题意：给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。

解法：利用KMP中next[ ]数组的性质，依次找到前缀、后缀匹配的字符串。

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int N=400010;
8 int next[N],a[N];
9 int n;
10 char s[N];
11
12 void kmp()
13 {
14 memset(next,0,sizeof(next));
15 int p=0;
16 next[1]=0;
17 for (int i=2;i<=n;i++) 18 { 19 while (s[i]!=s[p+1] && p) p=next[p]; 20 if (s[i]==s[p+1]) p++; 21 next[i]=p; 22 } 23 } 24 int main() 25 { 26 while (scanf("%s",s+1)!=EOF) 27 { 28 n=strlen(s+1); 29 kmp(); 30 int t=0; 31 for (int i=n;i;i=next[i]) 32 a[++t]=i; 33 for (int i=t;i>=1;i--)
34 printf("%d ",a[i]);
35 printf("\n");
36 }
37 return 0;
38 }