这个的题意与2046相近，不过要求的更多，是每个前缀都要求，而且数据加大了，每个前缀都要求，自然不能一次读取求next[],只能一个字符一个字符地读，读出一个字符，对其作kmp,利用kmp不回转的特点，算法复杂度 O(n)

#include<cstdio>
#include<cstring>
char data[1000010];
int next[1000010];
int length;
void getNext(char data[],int next[])
{
int i=0,j=-1;
next[0]=-1;
data[0]=getchar();//记得先读第一个字符，这里害我调试了好久，这里为什么要读一个字符，看了下面的++i,你就明白了
while(i<length)
{
if(j==-1||data[i]==data[j])
{
++i;
++j;
if(i%(i-j)==0&&i/(i-j)>1)//这三行是关键，这里正好是题目要的答案
printf("%d %d\n",i,i/(i-j));//
data[i]=getchar();   //继续读下一个字符
if(data[i]!=data[j])
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
}

int main()
{
int testCase=0;
while(scanf("%d",&length)&&length!=0)
{
getchar();//这个getchar()也不能少，亦害我调了好久
++testCase;
memset(data,0,sizeof(data));//这个容易理解，要使下一次的kmp生效，必须来一个null,因为null与前面所有字符均不等，故字符串的最后一个next值才是正确的
printf("Test case #%d\n",testCase);
getNext(data,next);
printf("\n");
}   
return 0;
}