For each prefix with length P of a given string S,ifS[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
【题解】
KMP水题，给你一个字符串str，对于每个str长度为p的前缀，如果str[i]==str[p+i](p+i<len)，那么认为它是一个periodic prefixs.求所有满足题意的前缀的长度p。
这题你只要发现一点就可以ac了，那就是next数组中的数与输出结果数之间的关系，我们用 {j=next[j];printf("%d ",j);} 输出的值是每个循环的初始位置，以样例二为例，这样输出的值依次为1,4,7,10,13，我们可以发现，这些值对应的位置都是a的位置（下标从1开始），但是我们要输出的是每个m的位置，这之间有什么联系呢？联系就是：串总长度len-j；那么上述例子按照这种结果输出就是15,12,9,6,3，这下看明白了吧，，只要把结果倒过来就是答案。
【AC代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int N=1000005;
int next_t[N];
char s1[N];
int len;void get_next() //next数组获取模板
{int i=0,j=-1;next_t[0]=-1;while(i<len){if(j==-1 || s1[i]==s1[j]){i++;j++;next_t[i]=j;}elsej=next_t[j];}
}
stack<int> q;void print()
{while(!q.empty()) q.pop();int xx=next_t[len];while(xx>=1)//压入栈中{q.push(xx);xx=next_t[xx];}int j=len;printf("%d\n",q.size()+1); //注意还有最后一个lenwhile(next_t[j]>=1){j=next_t[j];printf("%d ",len-j); //注意这层关系！！！}printf("%d\n",len);
}int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;++i){scanf("%s",s1);len=strlen(s1);get_next();printf("Case #%d: ",i);print();}return 0;
}才开始写KMP算法，，代码不美观 ，请见谅~~