首先给个博客：http://blog.csdn.net/lttree/article/details/20732385
感觉他说的很好，尤其是引用的那个博客，清晰的说明了循环节的两个公式。
http://www.cnblogs.com/jackge/archive/2013/01/05/2846006.html
那我就在重复一遍，这两个公式这的很重要。
对于这个循环节就是两个公式，
在i位置可以判断0~i-1的循环：
如果i%(i-next[i])==0 那么就有循环，并且next[i]!=0,
循环次数为 i/(i-next[i])
循环长度为 i-next[i]
这题还有一个坑的地方，我在代码里注释了，就是先要赋值dd，在循环，否则真的会超时，，，，坑死我了 = =
for (int i=2;i<=strlen(str);i++) 就是说这样是错的
#include <bits/stdc++.h>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long LL;
#define PI(A) printf("%d\n",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
//#define next Next
const double EPS= 1e- ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAXN= + ; //kuangbin 模板
//Next[]调用的时候不需要初始化
int Next[MAXN];
void kmp_pre(char x[])
{
int m=strlen(x);
int i,j;
j=Next[]=-;
i=;
while(i<m)
{
while(-!=j&&x[i]!=x[j]) j=Next[j];
Next[++i]=++j;
}
} char str[MAXN];
int N,k; int main()
{
while(~SI(N),N)
{
scanf("%s",str);
kmp_pre(str); //特别注意这里，一定要先把strlen(str)的值赋给dd 不能直接for (int i=2; i<=strlen(str); i++) 这样会TLE
int dd=strlen(str); printf("Test case #%d\n",++k);
//注意注意
for (int i=; i<=dd; i++)
{
int d=i-Next[i];
if (i%d==&&i>d)
{
printf("%d %d\n",i,i/d);
}
}
puts("");
}
return ;
}
第二遍，自己写的AC代码
#include <bits/stdc++.h>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long ll;
#define PU puts("");
#define PI(A) printf("%d\n",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e- ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAXN= + ;
int Next[MAXN];
int len;
char x[MAXN]; void kmp_pre()
{
int i,j;
j=Next[]=-;
i=;
while(i<len)
{
while(-!=j&&x[i]!=x[j])j=Next[j];
Next[++i]=++j;
}
}
int T;
int main()
{
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);
#endif
while(~SI(len),len)
{
scanf("%s",x);
kmp_pre();
printf("Test case #%d\n",++T);
for (int i=; i<=len; i++)
{
if (i%(i-Next[i])==&&Next[i]!=)
{
//i-Next[i]是循环串的长度，总长 除 循环串的长度就是 次数
// i / (i-Next[i])
printf("%d %d\n",i,i/(i-Next[i]));
}
}
PU;
}
return ;
}