【题解】FZU-1901 Period II

发表于 分类于 ， ， ， 本文字数： 668 阅读时长 ≈ 1 分钟
FZU-1901 Period II 类型 字符串 KMP next数组性质

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.

样例输入

1
2
3
4
5
4
ooo
acmacmacmacmacma
fzufzufzuf
stostootssto

样例输出

1
2
3
4
5
6
7
8
Case #1: 3
1 2 3
Case #2: 6
3 6 9 12 15 16
Case #3: 4
3 6 9 10
Case #4: 2
9 12

提示

无

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
char t[mxn];
int nxt[mxn], ans[mxn];

void getnxt(char* t, int m)
{
    int i = 0, j = -1; nxt[0] = -1;
    while (i < m)
    {
        if (j == -1 || t[i] == t[j]) {
            i++, j++;
            // if (t[i] == t[j])
            //     nxt[i] = nxt[j]; // next数组优化
            // else
                nxt[i] = j;
        } else
            j = nxt[j];
    }
}

int main()
{
    int T, cs=1; scanf("%d", &T);
    while(T--)
    {
        scanf("%s", t);
        int tl = strlen(t);
        getnxt(t, tl);

        int num = 0;
        for(int i=tl; i>0; i=nxt[i]){
            ans[num++] = tl-nxt[i];
        }
        printf("Case #%d: %d\n", cs++, num);
        for(int i=0; i<num; i++){
            if(i) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}