难度： 绿

算法： 字符串哈希

多次求字符串的子串是否相等，考虑字符串哈希。

记 $n$ 为字符串长度，$s_i$ 为字符串第 $i$ 项。

初始化出 $p_i=b^i$（此处 $b$ 为一个大质数，可取 $10^9+7$），算出 $h_i=h_{i-1}+s_i\times p_i$。特别的，$p_0=1$。

字符串哈希能够让你 $O(1)$ 复杂度内判断两个串是否相等。

字符串 $s_a...s_b$ 与 $s_c...s_d$ 相等，等价于：

在 $a\le b\le c\le d,b-a=d-c$ 的前提下。

以上运算均在 unsigned long long 意义下进行，通过自然溢出达到取模效果。

好的，讲完了。代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,p[1000010],h[1000100],b=1e6+7,f,x,ans;
string s;
int main(){
	p[0]=1;
	for(int i=1;i<=int(1e6);i++) p[i]=p[i-1]*b;
	for(;;){
		cin>>s;
		if(s==".") return 0;
		n=s.length(),ans=n;
		s="*"+s;
		for(ll i=1;i<=n;i++) h[i]=h[i-1]+s[i]*p[i];
		for(ll i=n;i>=1;i--){
			if(n%i!=0) continue;
			f=1;
			for(ll j=i;j<=n;j+=i){
				x=h[j]-h[j-i];
				if(x!=h[i]*p[j-i]){
					f=0;
					break;
				}
			}
			if(f) ans=min(ans,i);
		}
		printf("%llu\n",n/ans);
	}
}