Period
题意:一个长为N (2 <= N <= 1 000 000) 的字符串，问前缀串长度为k(k > 1)是否是一个周期串，即k = A...A;若是则按k从小到大的顺序输出k即周期数；
Sample Input
3 aaa
12 aabaabaabaab
Sample Output
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
题目其实是来自于LA的..挺好的一道题，用的是原版的kmp..
写写对KMP的理解:
这里写的kmp直接是从0开始的，并且0,1失配都指向0；kmp的getfail()其实就是用当前确定的p[i] = p[[f[i]]来给i+1一个匹配的机会，(特别注意不是相等)即f[i+1] = j+1;这就是失配边的下标转移；在i+1时，只是找了和p[i]相等的d[f[j]]，但是并没有去改变原来的匹配关系，这只是为了递推下去；
还有需要注意的就是kmp其实匹配到了第len位，这一位原本是'\0'的，但是由于里面的递推下一位的关系，这一位其实也是匹配了的；这道题就能用到第len的匹配关系～～很妙
思路:怎么知道前缀长度为2的串是是周期串?如aa?这时我们需要往后移到1位，我们怎么知道要往后一道以为呢？这正是f[i]的失配边的含义了~~由于若p[0] = p[1] = 'a';那么在p[2]失配时，显然朴素的KMP的f[2] = 1；这就弄成了周期；这也是为什么下面是从2开始到n的；
还有i代表的就是前缀的长度；即k(i - f[i]) = i,(k > 1)所以f[i] > 0并且(i-f[i])|i;
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e6 + ;
char p[N];
int f[N];
void getfail(char *p,int *f)
{
f[] = f[] = ;
int n = strlen(p);
for(int i = ;i < n;i++){
int j = f[i];
if(j && p[i] != p[j]) j = f[j];
f[i+] = (p[i] == p[j] ?j+:);// ｉ＋１会递推到第ｎ位
}
}
int main()
{
int n,kase = ;
while(scanf("%d",&n) == && n){
scanf("%s", p);
getfail(p,f);
printf("Test case #%d\n",kase++);
for(int i = ;i <= n;i++){// i = n **
if(f[i] > && i%(i-f[i])==)
printf("%d %d\n",i,i/(i-f[i]));
}
puts("");
}
}