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.

4

ooo

acmacmacmacmacma

fzufzufzuf

stostootssto

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
题意：求所有的循环节
思路：循环ans=ne[ans],len-ans

#include <iostream>

#include<string.h>

using namespace std;

const int maxn = 1e6+;

char a[maxn];

int ne[maxn],sum[maxn];

int main()

{

    int t;

    int num=;

    scanf("%d",&t);

    while(t--)

    {

        memset(ne,,sizeof(ne));

        scanf("%s",a+);

        int len=strlen(a+);

        for(int i=,j=;i<=len;i++)

        {

            while(j&&a[i]!=a[j+]) j=ne[j];

            if(a[i]==a[j+]) j++;

            ne[i]=j;

        }

        int ans=len,cnt=;

        while(ans)

        {

            ans=ne[ans];

            sum[++cnt]=len-ans;

        }

        printf("Case #%d: %d\n",++num,cnt);

        for(int i=;i<=cnt-;i++)

            printf("%d ",sum[i]);

        printf("%d\n",sum[cnt]);

    }

    return ;

}