link(南开中学oj)

AC代码

#include<cstdio>
using namespace std;
const int maxn=1e6+10;
int n,nxt[maxn];
char str[maxn];
int main(){
	scanf("%d%s",&n,str+1);
	int j=0;
	for(int i=2;i<=n;i++){
		while(j&&str[j+1]!=str[i]) j=nxt[j];
		if(str[j+1]==str[i]) j++;
		nxt[i]=j; 
	}
	for(int i=2;i<=n;i++)
		if(i%(i-nxt[i])==0&&nxt[i])
			printf("%d %d\n",i,i/(i-nxt[i]));
	return 0;
}

KMP求字符串周期怎么求，是什么原理