在Power String中，求一个字符串的循环节，应满足L mod (L-next[L])=0,则循环节长度为L-next[L]。
这个找next[L]的可以用hash。
#include<bits/stdc++.h>
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
",len/i);//得到循环节的个数
break;
}
}
}
}
return 0;
}
也可以用Kmp算法
#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
char s2[N];
int p[N],m;
void pre() //求next数组
{
memset(p,0,sizeof p);
for(int i=1,j=0;i<m;i++)
{
while(j>0&&s2[j+1]!=s2[i+1])j=p[j];
if(s2[i+1]==s2[j+1])j++;
p[i+1]=j;
}
}
signed main(){
while(~scanf("%s",s2+1))
{
if(s2[1]=='.')break;
m=strlen(s2+1);
pre();
if(m%(m-p[m])) //如果取模不0的话，则没有循环节
puts("1");
else
printf("%lld
",m/(m-p[m]));
}
return 0;
}
存在另一种形式的循环节,例如abcabca,此时如果将abc重写三次，得到abcabcabc,则原字符串为其前缀.
此时对于原字符串，其循环节长度为L-next[L]=7-4=3,循环节为abc.,不需要满足L mod (L-next[L])=0这个条件
证明如下:设abcabcab为s1s2....s8
因为next[8]=5,于是s[1..5]=s[4..8]于是s[1..3]=s[4..6]
原字符串: s1 s2 s3 s4 s5 s6 s7 s8
循环节构成 s1 s2 s3 s1 s2 s3 s1 s2 s3
蓝色那一段已相等了。
由上图可知s[1..2]=s[4..5],
而s[7..8]=s[4..5],于是s[1..2]=s[7..8],于是品红色那一段也相等了。
具体可见下面这个题
[Baltic2009]Radio Transmission
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input
第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.
Output
输出最短的长度
Sample Input
8
cabcabca
Sample Output
3
HINT
对于样例,我们可以利用"cab"不断自我连接得到"cabcabcab",读入的cabcabca,是它的子串
#include <cstdio>
#define MAXN 1000002
using namespace std;
char s[MAXN];
int next[MAXN];
int n;
void solve()
{
next[1] = 0;
int j = 0;
for (int i = 2; i <= n; i ++)
{
while ((j) && (s[j + 1] != s[i])) j = next[j];
if (s[j + 1] == s[i]) j ++;
next[i] = j;
}
printf("%d
", n - next[n]);
}
int main()
{
scanf("%d
%s", &n, s + 1);
solve();
return 0;
}
对于Milking Gird
Sol:
将大矩阵的每一列看成一个字符，然后对该大矩阵的每一列求出next[i]，则列最短循环节长度=小矩阵的宽=ans1=c-next[c]。
将大矩阵的每一行看成一个字符，然后对该大矩阵的每一行求出next[j]，则行最短循环节长度=小矩阵的高=ans2=r-next[r]。
最后答案：ans1*ans2即为所求矩阵的面积。
#include<bits/stdc++.h> using namespace std; char s[10010][100]; int next[10010]; int r,c; bool str1(int i,int j)//判断第i行和第j行是否相等 { for(int k=0;k<c;k++) if(s[i][k]!=s[j][k]) return false; return true; } bool str2(int i,int j)//判断第i列和第j列是否相等 { for(int k=0;k<r;k++) if(s[k][i]!=s[k][j]) return false; return true; } int main() { while(scanf("%d%d",&r,&c)==2) { for(int i=0;i<r;i++) scanf("%s",s[i]); next[0]=next[1]=0; for(int i=1;i<r;i++)//把每行看成一个字符 { int j=next[i]; while(j && str1(i,j)==false) j=next[j]; next[i+1] = (str1(i,j)==true)? j+1 :0; } int ans1=r-next[r]; next[0]=next[1]=0; for(int i=1;i<c;i++)//把每列看成一个字符 { int j=next[i]; while(j && str2(i,j)==false) j=next[j]; next[i+1] = (str2(i,j)==true)? j+1 :0; } int ans2=c-next[c]; printf("%d ",ans1*ans2); } } //原文链接：https://blog.csdn.net/u013480600/article/details/22990715