题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1358
题目大意： 给定一个字符串，求每个对应位置是否存在前缀重复串，如果存在输出位置及重复次数。
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int nextt[1000100]; void getnext(char *s){ //kmp算法的next数组 int len=strlen(s); int i=0,j=-1; nextt[0]=-1; while(i<len){ if(s[i]==s[j]||j==-1){ //判断是核心 nextt[++i]=++j; if(i%(i-j)==0&&i/(i-j)>1){ //注意这里i和j已经自加完成。由于kmp中next数组每个位置存的是上一个位置及之前的最大前后缀相同字母数，因此自加完成后指的就是当前位置，对这里的ij进行判断自然是正确的。 printf("%d %d\n",i,i/(i-j)); } } else j=nextt[j]; } } int main(){ char str[1000100]; int cnt=1; int n; while(scanf("%d",&n)!=EOF&&n){ memset(nextt,0,sizeof(nextt)); scanf("%s",str); printf("Test case #%d\n",cnt++); getnext(str); printf("\n"); //认真读题，避免presentation error } return 0; }如果题做不出来就找找样例的规律~
