求周期问题，简单KMP——
AC代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
const int N=1000005;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
int next[N],len,nextval[N];
char str[N];
void getnext(char *p)
{
int j=0,k=-1;
next[0]=-1;
while(j
if(k==-1||p[j]==p[k])
{
j++; k++;
next[j]=k;
}
else
k=next[k];
}
}
void getnextval(const char *p)
{
int i = 0,j =-1;
nextval[0]=-1;
while(i!=len)
{
if(j==-1||p[i]==p[j])
{
++i;++j;
if(p[i]!=p[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
int main()
{
int i,j,T,ca=0;
while(scanf("%d",&len)&&len)
{
scanf("%s",str);
getnext(str);
printf("Test case #%d\n",++ca);
for(i=2;i<=len;i++)
{
int t=i-next[i];
if(i%t==0&&i/t!=1)
printf("%d %d\n",i,i/t);
}
printf("\n");
}
return 0;
}