算法题之poj 1961 Period（KMP, 最短循环节）

算法题之poj 1961 Period（KMP, 最短循环节）2014-04-10题目链接：

POJ ： http://poj.org/problem？id=1961

HDU ： http://acm.hdu.edu.cn/showproblem.php？pid=1358

ZOJ ： http://acm.zju.edu.cn/onlinejudge/showProblem.do？problemCode=2177

题目大意：

给定一个长度为n的字符串s，求它的每个前缀的最短循环节。换句话说，对于每个i （2<=i<=n）,求一个最大的整数K>1（如果K存在），使得S的前i个字符组成的前缀是某个字符串重复K次得到的。输出所有存在K的i和对应的K。

比如对于字符串aabaabaabaab, 只有当i=2,6,9,12时K存在，且分别为2,2,3,4

分析与总结：

很经典的一道题目，各大OJ都有收录。

开始做这题的时候，刚刚看懂KMP，没看最短循环节的相关资料，自己乱搞，花了两节离散数学课想，结果终于AC了 = =，但不幸的是，结果发现只是再HDU和ZOJ过了，而poj的还是WA 。。。

然后学习《算法入门经典-训练指南》上面的方法，在poj上才成功AC。

虽然没能在poj上成功AC，但是经过这题的思考，对KMP的失配函数获取next的过程和原理有了更深的理解和体会。

代码：

1. 自己乱搞的代码， poj无法AC，求破

#include<cstdio>#include<cstring>const int MAXN = 1000005;char T[MAXN];intf[MAXN];int n;void getFail（char *P, int *f）{f[0]=f[1]=0;int start=1;int n=strlen（P）;bool flag=true; for（int i=1; i<n; ++i）{int j=f[i];while（j && P[i]！=P[j]）{flag=false;j=f[j];}if（P[i]==P[j]）{f[i+1]=j+1;if（f[i+1]==1）{flag=true;start=i;}if（flag && （i+1）>=start*2 && （i+1）%start==0）{printf（"%d %d
",i+1,（i+1）/start）;}}else{flag=true;start=i+1;f[i+1]=0;}}}int main（）{int cas=1;char ch;while（~scanf（"%d%*c",&n） && n）{printf（"Test case #%d
",cas++）;gets（T）;getFail（T,f）;puts（""）;}return 0;}