题目：Period
思路：
假如一段字符串有周期，那么 i - next[i]一定是最小周期长。
因为next[i]表示最长的相同前缀、后缀的长度，假设这个有周期的字符串一共有x个周期，此时，最长的相同的前缀、后缀是 第1到第x-1个周期 和 第2到第x个周期，则一个周期长就是 i-next[i]。
比如一个字符串为 abcabcabc，next=6，i=9，则周期长为3。
如果一个字符串的 i%( i - next[i] ) ! = 0 ，那么可以肯定这个字符串没有周期。因为如果它有周期，那么它一定可以被划分成整数个长度为 i - next[i] 的串。
注意：听说 noip 变量名用 next 会挂。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define maxn 1000000int n;
char a[maxn+5];
int nxt[maxn+5]={0};int main() {int T=0;while(~scanf("%d",&n)&&n!=0){printf("Test case #%d\n",++T);scanf("%s",a);nxt[0]=-1;for(int i=0;i<n;i++){int j=nxt[i];while(j>=0&&a[j]!=a[i]){j=nxt[j];}nxt[i+1]=++j;}for(int i=1;i<=n;i++){ if(nxt[i]&&i%(i-nxt[i])==0){printf("%d %d\n",i,i/(i-nxt[i]));}}printf("\n");}return 0;
}