记录编号	364633	评测结果	AAAAAAAAAA
题目名称	[POJ2406]字符串的幂	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2017-01-17 15:16:57	内存使用	5.06 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
const int maxn = 1000010;
char ch[maxn] = "\0";
int fail[maxn] = {0};
void GetFail(int n){
	int j = 0;fail[1] = 0;
	for(int i = 2;i <= n;i++){
		while(j>0&&ch[j+1]!=ch[i])j=fail[j];
		if(ch[i]==ch[j+1])j++;
		fail[i] = j;
	}
}

int main(){
	freopen("powerstrings.in","r",stdin);freopen("powerstrings.out","w",stdout);
	while(scanf("%s",ch+1)!=EOF&&ch[1]!='.'){
		int len = strlen(ch+1);
		GetFail(len);
		if(len - fail[len]!=0&&len % (len - fail[len]) == 0)printf("%d\n",len/(len - fail[len]));
		else printf("1\n");
	}
	return 0;
}