poj2752 Seek the Name, Seek the Fame
题意： 给出一个字符串S. 1 <= Length of S <= 400000.，找出所有S的前缀等于后缀的情况。按长度递增输出长度。相互之间用空格隔开。 比如： ababcababababcabab ab ab：2
abab abab：4
ababcabab ababcabab：9（正中间隔开）
ababcababababcabab ababcababababcabab：18（全部）
再比如： aaaaa a a：1
aa aa：2
aaa aaa：3
aaaa aaaa：4
aaaaa aaaaa：5
就是找出有多少个前缀等于后缀，然后输出长度就好了嘛。 如果有一个后缀等于一个前缀的话 那么他的p[]值不管怎么拐一定会拐回这个前缀的位置 所以我们只需要整理一下这些后缀的p[]值 然后输出 ovo 最后 输入为字符串，要加EOF不然RE不怪本宝宝 OVO
代码（是不是很简单呢）：
#include <cstdio> #include <cstring> using namespace std; int len,p[1000010],q[1000010],ans=0; char a[1000010]; int main() { while (scanf("%s",a+1)!=EOF) { len=strlen(a+1); int i,j=0;p[1]=0; for (i=2;i<=len;i++) { while (j>0&&a[i]!=a[j+1]) j=p[j]; if (a[i]==a[j+1]) j++; p[i]=j; } int t=len,ans=0; while (t!=0) { ans++; q[ans]=p[t]; t=p[t]; } for (i=ans-1;i>0;i--) { printf("%d ",q[i]); } printf("%d\n",len); } return 0; }