串应用- 计算一个串的最长的真前后缀

简介: 这篇文章提供了一个C++程序,用于找出给定字符串的最长真前后缀,并展示了如何通过计算每个子串的最长相同前后缀来实现这一功能。

C : 串应用- 计算一个串的最长的真前后缀

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 36     Solved: 24

串应用- 计算一个串的最长的真前后缀

题目描述

给定一个串,如ABCDAB,则 ABCDAB的真前缀有:{ A, AB,ABC, ABCD, ABCDA } ABCDAB的真后缀有:{ B, AB,DAB, CDAB, BCDAB }
因此,该串的真前缀和真后缀中最长的相等串为AB,我们称之为该串的“最长的真前后缀”。 试实现一个函数string
matched_Prefix_Postfix(string
str),得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty

输入

第1行:串的个数 n 第2行到第n+1行:n个字符串

输出

n个最长的真前后缀,若不存在最长的真前后缀则输出empty。

样例输入

6
a
ab
abc
abcd
abcda
abcdab

样例输出

empty
empty
empty
empty
a
ab

ac代码如下:

#include<iostream>
using namespace std;

int Get_next(string a)
{
    int i=0,k=-1;
    int len=a.length(),maxn=0;
    int *nextt=new int[a.length()+1];
    nextt[0]=-1;
    while(i<len)
    {
        if(k==-1||a[i]==a[k])
        {
            i++,k++;
            nextt[i]=k;
            if(k*2<=i)maxn=max(maxn,k);
            if(i/(i-k)%2==0)maxn=max(maxn,(i-k)*(i/(i-k)/2));
        }
        else k=nextt[k];
    }

    return maxn;
}
int get_maxnum(string a)
{
    int len=a.length(),maxn=0;
    for(int i=0;i<len;i++)
    {
        maxn=max(maxn,Get_next(a.substr(i,len)));
    }
    return maxn;
}
int main()
{
    string a;
    int n;
    cin>>n;
    while(n--)
    {
    cin>>a;
    int num=get_maxnum(a);
    if(!num)cout<<-1<<endl;
    else cout<<num<<endl;
    }
    return 0;
}
相关文章
|
算法 索引
【算法与数据结构】深入二叉树实现超详解(全源码优化)
【算法与数据结构】深入二叉树实现超详解(全源码优化)
220 1
|
算法 C++
B : DS串应用–串替换
这篇文章介绍了如何使用KMP算法在给定的主串中查找模式串的位置,并用替换串替换模式串的C++程序实现,仅考虑单次替换情况。
|
算法 C++
D : DS串应用—最长重复子串
这篇文章提供了一种C++程序,用于通过KMP算法计算给定字符串的最长不重叠重复子串的长度,如果没有重复子串则输出-1。
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
二叉树的中后序遍历构建及求叶子
二叉树的中后序遍历构建及求叶子
237 0
|
Java API
【亮剑】三种有效的方法来删除List中的重复元素Java的List
【4月更文挑战第30天】本文介绍了三种Java中删除List重复元素的方法:1) 使用HashSet,借助其不允许重复值的特性;2) 利用Java 8 Stream API的distinct()方法;3) 对自定义对象重写equals()和hashCode()。每种方法都附带了代码示例,帮助理解和应用。
1172 1
|
算法 Java
数据结构-构造哈夫曼树【详解+代码+图示】一文解惑!
数据结构-构造哈夫曼树【详解+代码+图示】一文解惑!
5762 1
|
网络协议 网络虚拟化
【HCIE】07.MPLS VPN单域(二)
【HCIE】07.MPLS VPN单域
166 0
问题 B: DS哈希查找—二次探测再散列(关键字互不相同
问题 B: DS哈希查找—二次探测再散列(关键字互不相同
193 0
|
Web App开发 iOS开发
CSS3 box-shadow 效果大全(内阴影,外阴影,三边阴影,双边阴影,单边阴影,细线描边…)
CSS3 box-shadow 效果大全(内阴影,外阴影,三边阴影,双边阴影,单边阴影,细线描边…)
953 0