kmp对我真无奈，我对kmp真苦恼。就是个算法嘛，我以为凭我脖子上的东西可以搞定，现在好了--搞得我头都大了。要我写个啥next的值，五个字：那都不是事。一到啥实际应用吧，我意识不行了，搞不清next到底有什么作用，能干什么。就好比见到了二分啊--

此题的意思呢，我弄了很久，其实是找相同串，比如ACMACMACMACMACMA，从后往前看next就行了，比如最后一个next[15] = 13，代表前13个字符串和后13位相同，直接用总长16 - 13 = 3，为一个解，接下来看next[13]了，一直这样找出结果，输出时一定注意格式，我交了4次全错在这里。

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

4oooacmacmacmacmacmafzufzufzufstostootssto

Sample Output

Case #1: 31 2 3Case #2: 63 6 9 12 15 16Case #3: 43 6 9 10Case #4: 29 12

#include 
       
        #include
        
         using namespace std;int a[1000100],next[1000100];int m;char s[1000100];void getNext(){    int j;    next[0] = 0; next[1] = 0;    for(int i = 1;i < m;i++)    {        j = next[i];        while(j && s[i]!=s[j])        {            j = next[j];        }        next[i+1] = s[i] == s[j]?j+1:0;    }}int main(){    int n,count,where = 1;    cin >> n;    while(n--)    {        cin >> s;        m = strlen(s);               // cout<< m;        count = 0;        int t = m;        getNext();        while(next[m])        {            a[count++] = t - next[m];            m = next[m];        }        cout << "Case #" << where <<": " << count+1 << endl;        where++;        for(int i = 0;i < count ;i++)        {            cout << a[i] << " ";        }        cout <
         
          << endl;    }    return 0;}