关于最小循环节的几种求法[原创]

对于任何信息，人类总有一种冲动，就是找到其最本质的组成。例如对于所有的数字，我们会去研究质数，那是因为质数可不可再分解的，于是任何整数都可以写成质因子连乘的形式。对于字符串，看似无规律，但由于语法上的原因，事实上许多字符串其用到的字符种类是不太多的，也就是说字母表中的26个字母出现的频率是不一样的。于是人类开始研究最小循环节，即某个字符串是不是由某个循环节字符串拼接而成。我们来看下面这个例题：

 Pku2406 Power Strings

求一个字符串由多少个重复的子串连接组成，例如ababab由3个ab连接而成，因此答案为3，又例如abcd由1个abcd连接而成，因此答案为1

Format

Input

多组数据，以"."代表测试结束 每组数据给出的字符串长度 <=1e6

Output

如题

样例输入

abcd

aaaa

ababab

.

样例输出

1

4

3

题解1：

对于这个题，我们设读入的字符串存在字符数组s中，设其长度为len.

于是可以枚举所求的循环节长度为i,即字符数组的前i个字符构成了循环节，然后就可以来进行校验了。由于此处涉及字符的比较，于是使用hash。

#include
#include
#include
#include
using namespace std;
typedef unsigned long long LL;
const LL base=131;
const int N=1000010;
int n;
LL power[N],sum[N];
bool check(LL v,int k) //判断s[1]~s[k]是否是循环节
{
for(register int i=1;i+k-1<=n;i+=k){
if(v!=sum[i+k-1]-sum[i-1]*power[k]) return 0;
}
return 1;
}
int main()
{
power[0]=1;
for(register int i=1;i<=N-10;++i) //hash准备工作
power[i]=power[i-1]*base;
char s[N];
while(scanf("%s",s+1)){
if(s[1]=='.')break;
n=strlen(s+1);
sum[0]=0;
for(register int i=1;i<=n;++i) sum[i]=sum[i-1]*base+LL(s[i]);
for(register int i=1;i<=n;++i){
if(n%i)continue;
LL expect=sum[i];
if(check(expect,i)){
printf("%d\n",n/i);
break;
}
}
}
return 0;
}

题解2:

在上种做法中，我们设循环节长度为i ,当然i必然为len的约数。于是整个字符串分成了len/i份。然后逐个逐个比较过去。大胆猜想一下，能否不要比较这么多次呢？

我们来画个图看看，对于字符串s划分如下：

为了区分，这几段标上了不同的颜色。

如果第一段为我们所求的循环节，则我们将s复写一次，并右移i 位

如果a2—a5这一段等于下面的a1—a4这一段，则可知

A2=a1,a3=a2,a4=a3,a5=a4.

于是循环节为A1.

分析出这个性质后，我们只需要一次字符之间的对比，就可以知道字符串的某个前缀是不是整个字符串的循环节了。

#include
using namespace std;
typedef unsigned long long ull;
char a[2000000];
int len=0;
ull sum[2000000],power[2000000];
ull get(int l,int r)
{
return sum[r]-sum[l-1]*power[r-l+1];
}
int main()
{
while(true)
{
scanf("%s",a+1);
len=strlen(a+1);
if(a[1]=='.'&&len==1)break;
memset(sum,0,sizeof(sum));
memset(power,0,sizeof(power));
for(int i=1;i<=len;i++)
sum[i]=sum[i-1]*193+ull(a[i])+1;
power[0]=1;
for(int i=1;i<=len;i++)
power[i]=power[i-1]*193;
for(int i=1;i<=len;i++) //暴力枚举循环节的长度
{
if(len%i!=0)continue;
else
{
ull a1=get(1,len-i),a2=get(i+1,len);
//注意是取长度为len-i的前缀，看是否等于长度为len-i的后缀
if(a1==a2)
{
printf("%d\n",len/i);//得到循环节的个数
break;
}
}
}
}
return 0;
}

Sol3:

 题解2中，减少了比较的次数，看上去似乎没有优化的地步了。我们将眼光转向循环节的长度这个要素。在前面的做法中，我们都只要求循环节长度i为总长度len的约数即可，于是划分的段数 k=len/i，完全没有考虑读入字符串的构成这个因素。很明显我们可以统计下字符串中每种字母出现的次数，不妨设之为sum1……sum26，当我们根据循环节将整个字符串划分成k段时，就是将这些字母“均分”到k段中，于是k至多为gcd(len,sum1,sum2….sum26),如果检测不成功，则也应该为 gcd(len,sum1,sum2….sum26)的约数，至此我们较为精确的约束了k范围，代码略过。