FZU 1901 Period II（KMP）

小咪咪 2022-06-09 01:11 170阅读 0赞

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

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.

Output

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.

Sample Input

4
    ooo
    acmacmacmacmacma
    fzufzufzuf
    stostootssto

Sample Output

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

题解：

话说这题的题意读了我好久。。。看了好多博客都没太看懂题意。。想了一上午也没想明白样例，心态爆炸，不想了直接看别人代码了，别人代码就是从后往前循环next数组，知道next为-1为止，每次i=next\[i\]，先求下个数再输出，注释就不打了，因为我根本就看！不！懂！题!语文太差的哭晕在厕所。。。。

ps：话说大多数博客题意完全是copy同一个博客的题意，敢问他们真的看懂了这题么？？

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int Next[1000005];
    char T[1000005];
    void init()
    {
        int i=0,j=-1;
        Next[0]=-1;
        while(T[i])
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else
                j=Next[j];
        }
    }
    int main()
    {
        int n,i,j,cas,ans,q,len;
        scanf("%d",&q);
        for(cas=1;cas<=q;cas++)
        {
            scanf("%s",T);
            init();
            ans=0;
            len=strlen(T);
            i=Next[len];
            while(i!=-1)
            {
                ans++;
                i=Next[i];
            }
            printf("Case #%d: %d\n",cas,ans);
            ans=0;
            i=Next[len];
            while(i!=-1)
            {
                ans++;
                if(ans==1)
                {
                    printf("%d",len-i);
                }
                else
                    printf(" %d",len-i);
                i=Next[i];
            }
            printf("\n");
        }
        return 0;
    }