题意
??给定一个字符串S,求该字符串每一个前缀的循环节长度,如果循环节长度不为1则输出(格式看题目)
解法
KMP :
??首先想这么一个问题:给定一个字符串S,由n 个子串重复得到,求最大的n
如果给定一个前缀Sk ,存在m,使得Skm=S ,显然有:|S| % k=0,而且S的前k 个字符必定等于S的后k 个字符。实际上这一个性质是m存在的充要条件
如果S 的前k个字符等于S 的后k个字符,那么可以把S 分为|S|k段,根据条件可以得到:第一段等于第二段,第二段等于第三段……因此存在一个m
那要如何判断S 的前k个字符是否等于S 的后k个字符?可以使用Next 数组:Nexti表示的对于前缀S1,S2,……Si中最长的一个前缀的长度,满足等长的后缀与其相等(不包括自身),因此我们只需要求出S的Next 数组,然后对于一个前缀Si(字符串从1开始),如果存在m使得有Cm=Si ,那么就必须满足i%i?Nexti=0 ,m=ii?Nexti
复杂度
O(T?n)
代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
const int L=1000010;
char s[L];
int Next[L],n;
void getNext()
{Next[0]=0;int i=1,j=0;while( i<=n-1 ){while( j && s[j]!=s[i] ) j=Next[j-1];if( s[j]==s[i] ) j=j+1;Next[i]=j;i=i+1;}
}
int main()
{int C=0;while( scanf("%d",&n)!=EOF ){if( !n ) break ;printf("Test case #%d\n",++C);for(int i=0;i<=n;i++) Next[i]=0;scanf("%s",s);getNext();for(int i=0,x;i<=n-1;i++){x=(i+1)/(i+1-Next[i]);if( x!=1 && x*(i+1-Next[i])==i+1 ) printf("%d %d\n",i+1,x);}printf("\n");}return 0;
}