POJ 2406 Power Strings（后缀数组或KMP或扩展KMP）

本文主要是介绍POJ 2406 Power Strings（后缀数组或KMP或扩展KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给你一个字符串求最多循环了多少次（这个题保证了最后一个循环节是完整的）

思路：

就是求最小循环节，这个问题可以用后缀数组,KMP,扩展KMP都能做出来，不过我个人觉得求最小循环节还是扩展KMP最好写了，KMP其次，后缀数组搞这个反而有点多余。。。不过既然论文提到了后缀数组的写法，那就写写好了
首先是扩展KMP，在求出扩展KMP的next数组后，找到第一个 $next[i]+i==len$ 且len%i=0的点，这个i就是最短循环节。
对于KMP，如果 $len-next[len]$ 不为len且next[i]%(len-next[i])为0，那么循环节就是 $len-next[len]$ ，否则最短循环节就是自身
对于后缀数组，枚举长度，如果len%i==0且rak[0]-rak[i]==1且height[rak[0]]==len-i就是一个合格的解，然而这题居然卡倍增的做法，所以代码以后补上

错误及反思：

代码：

首先是扩展KMP的做法：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn=1000100;
int anext[maxn];
char arr[maxn];
void getanext(char *str)
{int i=0,j,p=1,len=strlen(str);anext[0]=len;while(str[i]==str[i+1]&&i+1<len)i++;anext[1]=i;for(i=2;i<len;i++){if(anext[i-p]+i<anext[p]+p)anext[i]=anext[i-p];else{j=max(anext[p]+p-i,0);while(i+j<len&&str[j]==str[j+i])j++;anext[i]=j;p=i;}}
}int main(){while(scanf("%s",arr)&&arr[0]!='.'){getanext(arr);int len=strlen(arr);for(int i=1;i<=len;i++){if(anext[i]+i==len&&len%i==0){printf("%d\n",len/i);break;}}}}

然后是KMP的做法：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int len,nextval[1100000];
char w[1100000];
void get_next(){int j=0,k=-1;nextval[0]=-1;while(j<len){if(k==-1||w[k]==w[j])nextval[++j]=++k;else k=nextval[k];}
}
int main(){while(scanf("%s",w)){if(w[0]=='.') break;len=strlen(w);get_next();int l=len-nextval[len];if(l!=len&&nextval[len]%l==0)printf("%d\n",len/l);else printf("1\n");}
}