kmp杂题2 poj1961Period

poj1961 Period

题意： 给一个字符串，如果在前 i 位置处满足连续循环A^K（A：单位循环段，K：循环个数），则输出i和K（仅输出K>1的情况，按i的递增顺序）

是不是和上一题（poj2406） 有点像？ （不懂得童鞋可以看一看…顺便刷刷访问量哈哈） 像上一题那样把自己匹配一遍然后再lenb过一次就可以惹 是不是很简单？

放代码：

#include <cstdio> #include <cstring> using namespace std; int len,p[1000010],n=0; char a[1000010]; int main() { while (scanf("%d %s",&len,a+1)!=EOF) { n++; if (len==0) return 0; len=strlen(a+1); int i,j=0;p[1]=0; for (i=2;i<=len;i++) { while (j>0&&a[i]!=a[j+1]) j=p[j]; if (a[i]==a[j+1]) j++; p[i]=j; } printf("Test case #%d\n",n); for (i=2;i<=len;i++) { if (i%(i-p[i])==0&&i/(i-p[i])>1) printf("%d %d\n",i,i/(i-p[i])); } printf("\n"); } }