poj2406 Power Strings（kmp）

poj2406 Power Strings（kmp）

给出一个字符串，问这个字符串是一个字符串重复几次。要求最大化重复次数。

若当前字符串为S，用kmp匹配''+S和S即可。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=2e6+5;
char s1[maxn], s2[maxn];
int n1, n2, nxt[maxn], ans;

int main(){
	while (~scanf("%s", s1)){
		if (s1[0]=='.') break;
		memcpy(s2, s1, sizeof(s1));
		n1=n2=strlen(s1); 
		for (int i=n1; i<n1*2; ++i) s1[i]=s1[i-n1];
		n1*=2;
		int j=nxt[0]=-1;  //j:i-1的border位置 
		for (int i=1; i<n2; ++i){
			for (; ~j&&s2[j+1]!=s2[i]; j=nxt[j]); ++j;
			if (!j&&s2[0]!=s2[i]) j=-1;
			nxt[i]=j;
		} j=-1;  //j:s2中已经匹配完成的位置 
		for (int i=1; i<n1; ++i){
			for (; ~j&&s2[j+1]!=s1[i]; j=nxt[j]); ++j;
			if (j==n2-1){ ans=i-n2+1; break; }
			if (!j&&s2[0]!=s1[i]) j=-1;
		}
		printf("%d
", n2/ans);
	}
	return 0;
}