爱华网| Time Limit:2000MS | Memory Limit:65536K | |
| Total Submissions:6473 | Accepted:2991 |
Description
The little cat is so famous, that many couples tramp over hill anddale to Byteland, and asked the little cat to give names to theirnewly-born babies. They seek the name, and at the same time seekthe fame. In order to escape from such boring job, the innovativelittle cat works out an easy but fantasticalgorithm:Step1. Connect the father's name and the mother's name, to a newstring S.
Step2. Find a proper prefix-suffix string of S (which is not onlythe prefix, but also the suffix of S).
Example: Father='ala', Mother='la', we have S = 'ala'+'la' ='alala'. Potential prefix-suffix strings of S are {'a', 'ala','alala'}. Given the string S, could you help the little cat towrite a program to calculate the length of possible prefix-suffixstrings of S? (He might thank you by giving your baby aname:)
Input
The input contains a number of test cases. Each test case occupiesa single line that contains the string S describedabove.Restrictions: Only lowercase letters may appear in the input.1<= Length ofS<=400000.
Output
For each test case, output a single line with integer numbers inincreasing order, denoting the possible length of the new baby'sname.Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
题意：找串的前缀与后缀匹配长度；主要理解next[i]的意义。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int next[1000010],m;
char s[1000010];
void get_next()
{int i=0,j=-1;
next[0]=-1;
while(i<m)
{if(j==-1||s[i]==s[j])
{i+=1;
j+=1;
next[i]=j;
}
else j=next[j];
}
}
void output(int n)
{if(next[n]!=0)
{output(next[n]);
printf("%d ",next[n]);}
}
int main()
{ while(scanf("%s",s)!=EOF) {m=strlen(s);
get_next();
output(m);
printf("%dn",m);}
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////
引用：http://blog.sina.com.cn/s/blog_6ec5c2d00100tnah.html
#include<iostream>
#include<string.h>
usingnamespacestd;
charP[400010];
intpre[400010];
intm;
voidCOMPUTE_PREFIX_FUNCTION(char*P)
{
pre[1] =0;
intq = 0;
for(inti=2; i<=m; i++)
{
while(q>0 && P[q+1] != P[i])
q = pre[q];
if(P[q+1] == P[i])
q++;
pre[i] = q;
}
}
voidoutput(inti)
{
if(pre[i]!=0)
{
output(pre[i]);
printf("%d ",pre[i]);
}
}
intmain()
{
while(scanf("%s",P)!=EOF)
{
m = strlen(P);
for(inti=m; i>=1; i--)
P[i] = P[i-1];
COMPUTE_PREFIX_FUNCTION(P);
output(m);
printf("%dn",m);
}
return0;
}
