关于最小循环节的几种求法关于最小循环节的几种求法

对于任何信息，人类总有一种冲动，就是找到其最本质的组成。例如对于所有的数字，我们会去研究质数，那是因为质数可不可再分解的，于是任何整数都可以写成质因子连乘的形式。对于字符串，看似无规律，但由于语法上的原因，事实上许多字符串其用到的字符种类是不太多的，也就是说字母表中的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范围，代码略过。