[FZU 1901]Period II KMP

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数组可以递归的求该字符串每个匹配的前缀和后缀的长度

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000+10;
char s[maxn];
int Next[maxn];
int ans[maxn];

void getNext()
{
    int len = strlen(s);
    int j = 0;
    int t = Next[0] = -1;
    while (j < len) {
        if (t == -1 || s[j] == s[t])
            Next[++j] = ++t;
        else
            t = Next[t];
    }
}

int main() 
{
    //freopen("1.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        scanf("%s", s);
        int cnt = 0;
        int len = strlen(s);
        getNext();
        int i = Next[len];
        ans[cnt++] = len-i;
        while (Next[i] >= 0) {
            i = Next[i];
            ans[cnt++] = len-i;
        }
        printf("Case #%d: %d
", t, cnt);
        for (int i = 0; i < cnt-1; i++)
            printf("%d ", ans[i]);
        printf("%d", ans[cnt-1]);
        printf("
");
    }


    return 0;
}