算法题：HDU 3746 Cyclic Nacklace（KMP，最短循环节）

算法题：HDU 3746 Cyclic Nacklace（KMP，最短循环节）2014-03-17 csdn博客 shuangde800链接：

http://acm.hdu.edu.cn/showproblem.php？pid=3746

题目大意：

给定一个字符串T，在T后面添加x个字符串（让x最小），使得新字符串由前缀字串至少循环两次构成的。

例如，

abca, 只需要再添加2个字母bc，形成abcabc,就变成了由abc循环两次构成的。

分析与总结：

失配函数构造next数组的性质的应用，需要对这个有真正的理解。

对于长度为len的字符串，假设已经够造完了next数组，那么len-next[len]就是这个字符串的最小循环节。

如果正好len%（len-next[len]）==0就说明正好组成完成的循环。

否则，说明还需要再添加几个字母才能补全。

需要补的个数是循环个数len-next[len]-f[len]%（len-next[len]）.

f[len]%（len-next[len]）表示在最后一个循环节中已经构造了这么多个数。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 100005;char T[MAXN];intf[MAXN];void getFail（char* p,int* f）{int n=strlen（p）;f[0]=f[1]=0;for（int i=1; i<n; ++i）{int j=f[i];while（j && p[i]！=p[j]） j=f[j];f[i+1] = p[i]==p[j]？1+j:0;}}int main（）{int nCase;scanf（"%d",&nCase）;while（nCase--）{scanf（"%s",T）;int len=strlen（T）;getFail（T, f）;if（f[len] && len%（len-f[len]）==0）{puts（"0"）;}else{int ans=（len-f[len]）-f[len]%（len-f[len]）;printf（"%d
",ans）;}}return 0;}