POJ 2752 next数组

链接：

题意：

求一个串所有的前缀等于后缀的子串长度

题解：

求一个next数组，然后递归输出就行了

代码：

31 char a[MAXN];
32 int nex[MAXN];
33 int n;
34 
35 void build_next() {
36     nex[1] = 0;
37     int j = 0;
38     rep(i, 2, n + 1) {
39         while (j > 0 && a[j + 1] != a[i]) j = nex[j];
40         if (a[j + 1] == a[i]) j++;
41         nex[i] = j;
42     }
43 }
44 
45 void output(int x) {
46     if (nex[x] == 0) {
47         printf("%d", x);
48         return;
49     }
50     output(nex[x]);
51     printf(" %d", x);
52 }
53 
54 int main() {
55     while (scanf("%s", a + 1) != EOF) {
56         memset(nex, 0, sizeof(nex));
57         n = strlen(a + 1);
58         build_next();
59         output(n);
60         cout << endl;
61     }
62     return 0;
63 }