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
题解：
话说这题的题意读了我好久。。。看了好多博客都没太看懂题意。。想了一上午也没想明白样例，心态爆炸，不想了直接看别人代码了，别人代码就是从后往前循环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;}elsej=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);}elseprintf(" %d",len-i);i=Next[i];}printf("\n");}return 0;
}