Period II(FZU-1901)

题面

For each prefix with length P of a given string S,if

S[i]=S[i+P] for i in [0..SIZE(S)-p-1],

then the prefix is a “period” of S. We want to all the periodic prefixs.

输入

Input contains multiple cases.

The first line contains an integer T representing the number of cases. Then following T cases.

Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.

输出

For each test case, first output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.

样例输入

14
2ooo
3acmacmacmacmacma
4fzufzufzuf
5stostootssto

样例输出

1Case #1: 3
21 2 3
3Case #2: 6
43 6 9 12 15 16
5Case #3: 4
63 6 9 10
7Case #4: 2
89 12

提示

无

思路

类似【题解】POJ-2752 Seek the Name, Seek the Fame。对于字符串的所有前缀，若存在循环节，输出符合条件的前缀个数与这个前缀字符串的长度。注意输出格式，行尾不得有多余空格。

代码

 1char t[mxn];
 2int nxt[mxn], ans[mxn];
 3
 4void getnxt(char* t, int m)
 5{
 6    int i = 0, j = -1; nxt[0] = -1;
 7    while (i < m)
 8    {
 9        if (j == -1 || t[i] == t[j]) {
10            i++, j++;
11            // if (t[i] == t[j])
12            //     nxt[i] = nxt[j]; // next数组优化
13            // else
14                nxt[i] = j;
15        } else
16            j = nxt[j];
17    }
18}
19
20int main()
21{
22    int T, cs=1; scanf("%d", &T);
23    while(T--)
24    {
25        scanf("%s", t);
26        int tl = strlen(t);
27        getnxt(t, tl);
28
29        int num = 0;
30        for(int i=tl; i>0; i=nxt[i]){
31            ans[num++] = tl-nxt[i];
32        }
33        printf("Case #%d: %d\n", cs++, num);
34        for(int i=0; i<num; i++){
35            if(i) printf(" ");
36            printf("%d", ans[i]);
37        }
38        printf("\n");
39    }
40    return 0;
41}