算法题：HDU 3746 Cyclic Nacklace(KMP，最短循环节)

链接：

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];
int  f[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\n",ans);
        }
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， 字符串
， include
， 循环
， 路径最短
， len
， 循环添加
， 个数
， 字符串测试acm数组
， 字符循环
最短
cyclic nacklace、nacklace、手游3746、rj173746解压密码、rj173746 王元姬，以便于您获取更多的相关知识。