题目描述
如果一个字符串(S)是由一个字符串(T)重复(K)次形成的，则称(T)是(S)的循环元。使(K)最大的字符串(T)称为(S)的最小循环元，此时的(K)称为最大循环次数。
现给一个给定长度为N的字符串(S)，对(S)的每一个前缀(S[1)~(i])，如果它的最大循环次数大于(1)，则输出该前缀的长度和最大循环次数。
分析
引理
(S[1)-(i])具有长度(len<i)的循环元的充要条件是(len)能整除(i)并且(S[len+1)-(i]=S[1)~(i-len])(即(i-len)是(KMP)算法中(next[i])的"候选择")
证明:
首先,(len)能作为(S)的循环元,必须满足(len)能整除(i),且(S[len+1)-(i])和(S[1)-(i-len])都是由(i/len-1)个循环元构成的,即(S[len+1)-(i]=S[1)-(i-len])
其次,分别从(S[len+1)-(i])和(S[1)-(i-len])取前(len)个字符,可以发现(S[len+1)-(2*len]) (=) (S[1)-(len]),依此类推,可以发现(S[len+1)-(i])和(S[1)-(i-len])是以(len)为间隔错位对齐的,故(S[1)-(len])是(S)的循环元
证毕
(code)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int n;
int next[MAXN];
char s[MAXN],s2[MAXN];
void pre(){
int j = 0;
for(int i=2;i<=n;i++){
while(j>0&&s[i]!=s[j+1]) j = next[j];
if(s[i]==s[j+1]) j++;
next[i] = j;
}
}
int main(){
int t;
cin>>t;
int now = 0;
while(t--){
now++;
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
pre();
printf("Test case #%d
", now);
for(int i=1;i<=n;i++)
if(i%(i-next[i])==0&&i/(i-next[i])>1){
cout<<i<<" "<<i/(i-next[i])<<endl;
}
}
}
参考资料
《算法竞赛进阶指南》-李煜东