【kmp算法—最小循环节】Cyclic Nacklace HDU - 3746

叁歲伎倆 2022-06-07 02:15 180阅读 0赞

Think:  
1知识点：kmp算法—最小循环节  
2题意：输入一个原始字符串，选择在头部或者尾部添加别的字符，使得新的字符串为一个周期循环字符串，询问最小需要添加几个字符  
3题意分析：求最小循环节  
（1）：最小循环节：cir\_len = len - next\[len-1\]  
（2）：如果cir\_len != len && len%cir\_len == 0则不需要再添加，除此之外，添加的字符数为cir\_len - len%cir\_len;

[vjudge题目链接][vjudge]  
[建议参考博客1-参考博主的题意分析][1-]  
[建议参考博客2-参考博主的代码实现][2-]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int size_P = 100414;
    
    int _next[size_P];
    char st[size_P];
    
    void get_next(char *P, int len_P);
    
    int main(){
        int T, cir_len;
        scanf("%d", &T);
        while(T--){
            scanf("%s", st);
            int len_P = strlen(st);
            get_next(st, len_P);
            cir_len = len_P - _next[len_P-1];/*计算最小循环节长度*/
            if(cir_len != len_P && len_P%cir_len == 0) printf("0\n");
            else printf("%d\n", cir_len - len_P%cir_len);
        }
        return 0;
    }
    void get_next(char *P, int len_P){
        int q, k;
        _next[0] = 0;
        k = 0;
        for(q = 1; q < len_P; q++){
            while(k > 0 && P[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
    }

[vjudge]: https://vjudge.net/problem/HDU-3746
[1-]: http://blog.csdn.net/HHH_go_/article/details/70143425
[2-]: http://www.cnblogs.com/gongxijun/p/3878080.html