【UVA1328】Period

题意

??给定一个字符串$S$，求该字符串每一个前缀的循环节长度，如果循环节长度不为1则输出（格式看题目）

解法

$KMP$：
??首先想这么一个问题：给定一个字符串$S$，由$n$个子串重复得到，求最大的$n$
如果给定一个前缀$S_k$，存在$m$，使得${S_k}^m=S$，显然有：$|S|$ % $k=0$，而且$S$的前$k$个字符必定等于$S$的后$k$个字符。实际上这一个性质是$m$存在的充要条件
如果$S$的前$k$个字符等于$S$的后$k$个字符，那么可以把$S$分为$\dfrac{|S|}{k}$段，根据条件可以得到：第一段等于第二段，第二段等于第三段……因此存在一个$m$
那要如何判断$S$的前$k$个字符是否等于$S$的后$k$个字符？可以使用$Next$数组：$Next_i$表示的对于前缀$S_1，S_2，……S_i$中最长的一个前缀的长度，满足等长的后缀与其相等（不包括自身），因此我们只需要求出$S$的$Next$数组，然后对于一个前缀$S_i$（字符串从1开始），如果存在$m$使得有$C^m=S_i$，那么就必须满足$i$%$i-Next_i=0$，$m=\dfrac{i}{i-Next_i}$

复杂度

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;
}