【POJ1961】最短周期串/最大周期 kmp

引理：(s[1,i]) 具有长度为 (len) 的循环节的充要条件是：(len | i，s[1,i-len]=s[len+1,i])。

代码如下

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e6+10;

char s[maxn];
int n,kase,fail[maxn];

void get_fail(){
	fail[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j&&s[i]!=s[j+1])j=fail[j];
		if(s[i]==s[j+1])++j;
		fail[i]=j;
	}
}

void read_and_parse(){
	scanf("%s",s+1);
	get_fail();
}

void solve(){
	for(int i=2;i<=n;i++)
		if(i%(i-fail[i])==0&&i/(i-fail[i])>1)
			printf("%d %d
",i,i/(i-fail[i]));
	puts("");
}

int main(){
	while(scanf("%d",&n)&&n){
		printf("Test case #%d
",++kase);
		read_and_parse();
		solve();
	}
	return 0;
}