poj 2752

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define N 400000
 6 using namespace std;
 7 
 8 char s[N];
 9 int next[N], a[N];
10 void getnext(char *p, int *next)
11 {
12     int i = 0, j = -1, len = strlen(p);
13     next[0] = -1;
14     while (i < len)
15     {
16         if (j == -1 || p[j] == p[i])
17         {
18             i++; j++; next[i] = j;
19         }
20         else j = next[j];
21     }
22 }
23 int main(void)
24 {
25     freopen("poj2752.in", "r", stdin);
26     while (~scanf("%s", s))
27     {
28         getnext(s, next);
29         int len = strlen(s), i, k = 0;
30         i = len;
31         a[0] = len;
32         while (next[i] > 0)
33         {
34             i = next[i];
35             a[++k] = i;
36         }
37         for (int j = k; j >= 0; --j)
38         {
39             printf("%d", a[j]);
40             if (j) printf(" ");
41         }
42         printf("\n");
43     }
44 
45     return 0;
46 }

这道题目要求既是前缀字符串又是后缀字符串的所有可能的长度，正好运用了KMP算法里面next数组的意义，要保证结果是针对整个字符串的，所以在next数组中从后往前扫描即可，因为，next数组中，越往后，数字就越大，并且表示的是后缀和前缀相同的最大长度，所以所得到的结果顺序是反的，要求从小到大输出，逆序输出就可以了。