【kmp算法next数组求解公共前后缀】Seek the Name, Seek the Fame POJ - 2752

爱被打了一巴掌 2022-06-07 02:25 110阅读 0赞

Think:  
1知识点：通过kmp算法next数组求解公共前后缀  
2题意：输入串s，输出所有的符合条件的子串的长度，符合条件：子串既是s的前缀又是s的后缀  
3解题知识点：  
（1）：前缀定义：从s的开始字符到s的任意字符为止  
（2）：后缀定义：从s的任意字符到s的最后字符为止  
（3）：next\[i\]定义：字符s\[i\]及其前面至多有next\[i\]个连续的字符和字符串s从初始位置开始的next\[i\]个字符匹配  
4解题思路：  
求解next数组，然后递归输出路径，注意len\_P需要单独输出

[vjudge题目链接][vjudge]

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

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int size_P = 400414;
    
    int _next[size_P];
    char st[size_P];
    
    void get_next(char *P, int len_P);
    void pri_path(int n);
    
    int main(){
        while(~scanf("%s", st)){
            int len_P = strlen(st);
            get_next(st, len_P);
            pri_path(_next[len_P-1]);
            printf("%d\n", len_P);
        }
        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;
        }
        return;
    }
    void pri_path(int n){
        if(n == 0) return;
        pri_path(_next[n-1]);
        printf("%d ", n);
        return;
    }

[vjudge]: https://vjudge.net/problem/POJ-2752
[Link 1]: http://blog.csdn.net/tigerisland45/article/details/51765166