【kmp算法next数组-串的最小循环节/循环周期】Period HDU - 1358

迈不过友情╰ 2022-06-07 02:22 174阅读 0赞

Think:  
1知识点：通过kmp算法的next数组求解串的最小循环节和循环周期  
2题意：一个长为N (2 <= N <= 1 000 000) 的字符串，询问前缀串长度为k(k > 1)的串是否是一个周期串，即k = A…A;若是则按k从小到大的顺序输出k和周期数  
3解题知识点：  
（1）：一个串的最小循环节长度：len - next\[len\]  
（2）：若len%(len-next\[len\]) == 0, 则这个字符串的最小周期为len/(len-next\[len\])

[vjudge题目链接][vjudge]

[建议参考博客—参考博主题意][Link 1]

以下为Presentation Error代码—题目要求每组测试数据之后需要输出空行

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int size_P = 1000414;
    
    int _next[size_P];
    char st1[size_P];
    
    void get_next(char *P, int len_P);
    
    int main(){
        int k = 1;
        int n, i, cir_len;
        while(~scanf("%d", &n) && n){
            scanf("%s", st1);
            get_next(st1, n);
            printf("Test case #%d\n", k++);
            for(i = 1; i <= n; i++){
                cir_len = i - _next[i-1];
                if(cir_len != i && i%cir_len == 0)
                    printf("%d %d\n", i, i/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[k] != P[q]){
                k = _next[k-1];
            }
            if(P[k] == P[q])
                k++;
            _next[q] = k;
        }
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int size_P = 1000414;
    
    int _next[size_P];
    char st1[size_P];
    
    void get_next(char *P, int len_P);
    
    int main(){
        int k = 1;
        int n, i, cir_len;
        while(~scanf("%d", &n) && n){
            scanf("%s", st1);
            get_next(st1, n);
            printf("Test case #%d\n", k++);
            for(i = 1; i <= n; i++){
                cir_len = i - _next[i-1];
                if(cir_len != i && i%cir_len == 0)
                    printf("%d %d\n", i, i/cir_len);
            }
            printf("\n");
        }
        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[k] != P[q]){
                k = _next[k-1];
            }
            if(P[k] == P[q])
                k++;
            _next[q] = k;
        }
    }

[vjudge]: https://vjudge.net/problem/HDU-1358
[Link 1]: http://www.cnblogs.com/hxer/p/5268201.html