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;
}