http://acm.hdu.edu.cn/showproblem.php?pid=1358
几天看了kmp,觉得其实挺有趣的,可是当自己做题的时候才知道,它的用法是很灵活的,当计算重复子串的时候最好next的下标为-1开始,并且要注意数组的大小,因为数组开小了,所以一直wa。。。
代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[1000000];
int len,next[1000000];
int main()
{
int t=0,a;
while(scanf("%d",&len),len)
{
scanf("%s",s);
printf("Test case #%d\n",++t);
next[0]=-1; int i=0,j=-1;
while(len>i)
{
if(j==-1||s[i]==s[j])
{
++i;++j;
next[i]=j;
}
else
j=next[j];
}
for(int k=1;k<=len;++k)
{
// printf("k:%d %d\n",k,next[k]);
if(!(k%(k-next[k]))&&next[k]!=0)
{
a=k/(k-next[k]);
printf("%d %d\n",k,a);
}
}
printf("\n");
}
// system("pause");
return 0;
}