- 题意
给定两个字符串a和b,我们定义ab为他们的连接。例如，如果a=”abc” 而b=”def”， 则a*b=”abcdef”。 如果我们将连接考虑成乘法，一个非负整数的乘方将用一种通常的方式定义：a^0 =””(空字符串)，a^(n+1)=a(a^n)。
对于每一个s，你应该打印最大的n，使得存在一个a，让s=a^n.
- 思路
kmp计算next数组，其中next[i]表示最长相等前后缀。
若s可以表示为最小的x循环节的n次方，则n=len/(len-next[len])
s = x x x x x，next[len]=4x
故循环节数n=len/(len-next[len])
而若s无循环节，那么len % (len - next[len]) != 0或next[len]<len/2,此时n=1.
- 时间复杂度O(n)
/*
kmp计算next数组，其中next[i]表示最长相等前后缀。
若s可以表示为最小的x循环节的n次方，则n=len/(len-next[len])
s = x x x x x，next[len]=4x
故循环节数n=len/(len-next[len])
而若s无循环节，那么len % (len - next[len]) != 0或next[len]<len/2,故n=0
*/
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#define N 1000005
using namespace std;
int n[N];
void calNext(char* s) {
memset(n, 0, sizeof(n));
int i = 0, k = -1;
n[0] = -1;
int len = strlen(s);
while (i < len) {
while (k >= 0 && s[i] != s[k])
k = n[k];
k++, i++;
n[i] = k;
}
}
int main() {
char s[N];
while (scanf("%s", s)) {
if (s[0] == '.'&&strlen(s) == 1) break;
calNext(s);
int len = strlen(s);
int ans = 1;
if (len % (len - n[len]) == 0) ans = len / (len - n[len]);
printf("%d\n",ans);
}
return 0;
}
