【题目链接】

ybt 1457：Power Strings

【题目考点】

1. 字符串哈希

相关知识见：【模板：字符串哈希】LOJ #103. 子串查找

2. KMP算法

相关知识见：[【模板：KMP算法】]

【解题思路】

对于每个给定的字符串，求该字符串最小循环节的循环次数。
以下会使用python字符串切片写法来表示字符串的子串。

解法1：字符串哈希

字符串$s$的循环节的长度一定是$s$的长度$n$的约数。
从小到大枚举字符串$s$的长度$n$的约数$l$，将$s$分为多个长为$l$的子串，判断每个子串是否相同。
构造将字符串$s$当做$base$进制数，求出该数的数值作为哈希值，哈希值使用unsigned类型保存，进行自然溢出。
求出字符串$s$的哈希数组$h$，$h_i$表示$s$的前$i$个字符构成的子串，即$s[:i]$的哈希值，满足递推式$h_i=h_{i-1}base+c_{i]}$（$c_i$为$s$的第$i$个字符转为的数值)，可以递推求出。
那么$s$的循环节为$s$前$l$个字符构成的子串$s[:l]$，该子串的哈希值为$h_l$。
根据字符串哈希算法，$s$从下标$i$开始长为$l$的子串$s[i:i+l]$的哈希值为$h_{i+l}-h_{i}bas{e}^l$
如果字符串$s$的每个长为$l$的子串的哈希值都和前$l$个字符构成的子串$s[:l]$的哈希值相同，那么$l$就是该字符串的最短循环节，$n/l$为最短循环节出现的次数。

初始化哈希数组的时间复杂度为$O(n)$
对于每个$n$的约数$l$，需要最多循环$n/l$次来判断长度$l$是否为字符串$s$的循环节的长度。每次循环可以以$O(1)$时间复杂度比较两个字符串的哈希值是否相同。不考虑出现哈希冲突的情况下，哈希值相同可以近似理解为原字符串相同。
最大总循环次数为
${\sum }_{l|n}\frac{n}{l}=n{\sum }_{l|n}\frac{1}{l}<n{\sum }_{l=1}^n\frac{1}{l}$
${\sum }_{l=1}^n\frac{1}{l}<{\int }_{x=1}^n\frac{1}{x}dx=\ln x{|}_1^n=\ln n$
所以：${\sum }_{l|n}\frac{n}{l}<n\ln n$
其时间复杂度为$O(n\log n)$。$n$最大为$10^6$，如果是一组数据，该算法可以保证通过此题。
多组数据问题，如果没有明确给出数据组数，可以认为数据组数小于10组。
实际执行过程中，$l$从小到大的循环次数以及对所有长为$n/l$子串判断其是否等于$s[:l]$的过程的循环次数都不会达到最大，因此实际的运算次数会比估算的数值更小。该算法最终通过了此题。

解法2：KMP算法

已知长为$n$的字符串$s$的最短循环节长度为$n-next[n]$
其中$next$数组为字符串$s$的前缀数组，$next[i]$表示$s[:i]$的最长相等前后缀的长度，可以通过KMP算法求出。
如果字符串由若干完整的循环节构成，必须满足$n$是最短循环节长度$n-next[n]$的倍数。循环次数为：$n/(n-next[n])$

【题解代码】

解法1：字符串哈希

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
string s;
unsigned bp[N], h[N], base = 31;
void initBp()
{
	bp[0] = 1;
	for(int i = 1; i < N; ++i)
		bp[i] = bp[i-1]*base;
}
bool check(int l, int len)//判断s的循环节长度能否为l 
{
	for(int i = l; i < len; i += l)//看s[i:i+l]是否与s[:l]一样 
		if(h[l] != h[i+l]-h[i]*bp[l]) 
			return false;
	return true; 
}
int main()
{
	initBp();
	while(cin >> s && s != ".")
	{
		int len = s.length();
		for(int i = 1; i <= len; ++i)
			h[i] = base*h[i-1]+s[i-1]-'A'+1;
		for(int l = 1; l <= len; ++l) if(len%l == 0 && check(l, len))//l：子串长度，是len的因数 
		{
			cout << len/l << endl;//输出循环节的个数 
			break;
		}
	}
	return 0;
}

解法2：KMP算法

#include <bits/stdc++.h>
using namespace std;
#define N 1000005 
int Next[N];
int main()
{
	string s;
	while(cin >> s && s != ".")
	{
		int i = 0, j = Next[0] = -1, ls = s.length();
		while(i < ls)
		{
			if(j == -1 || s[i] == s[j])
				Next[++i] = ++j;
			else
				j = Next[j];
		}
		if(ls%(ls-Next[ls]) == 0)//如果是完整的由循环节构成的字符串 
			cout << ls/(ls-Next[ls]) << endl;
		else
			cout << 1 << endl;
	}
	return 0;
}