hdoj3746（kmp算法的nex数组求最小循环节）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://vjudge.net/problem/HDU-3746

题意：给定一个字符串，问最少在两端添加多少元素使得整个字符串是呈周期性的。

思路：

应用到kmp中nex数组的性质，数组的最小循环节是L=len-nex[len]，证明见http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html。

如果len%L==0，那么输出0.

否则输出L-len%L。

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int maxn=1e5+;
int T,len,nex[maxn];
char s[maxn];void get_next(){
int j;
j=nex[]=-;
for(int i=;i<len;++i){
while(j>-&&s[i]!=s[j+]) j=nex[j];
if(s[i]==s[j+]) ++j;
nex[i]=j;
}
}int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);
len=strlen(s);
get_next();
int t1=len-,t2=nex[t1];
if(t2==-){
printf("%d\n",len);
}
else{
int t3=len-(t2+);
if(len%t3==){
printf("0\n");
}
else{
printf("%d\n",t3-len%t3);
}
}
}
return ;
}