hdu1358 Period kmp求循环节

链接

http://acm.hdu.edu.cn/showproblem.php?pid=1358

思路

当初shenben学长暑假讲过，当初太笨了，noip前几天才理解过来、、
我也没啥好说的

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+7;
int n,len,fail[N];
char s[N];
void get_fail() {
	int p=0;
	for(int i=2;i<=len;++i) {
		while(s[p+1]!=s[i]&&p>0) p=fail[p];
		if(s[p+1]==s[i]) p++;
		fail[i]=p;
	}
}
int AK;
void solve() {
	memset(fail,0,sizeof(fail));
	get_fail();
	printf("Test case #%d
",++AK);
	for(int i=2;i<=len;++i) {
		if(fail[i]&&i%(i-fail[i])==0) {
			printf("%d %d
",i,i/(i-fail[i]));
		}
	}
	puts("");
}
int main() {
	while(233) {
		scanf("%d",&len);
		if(!len) break;
		scanf("%s",s+1);
		solve();
	}
	return 0;
}