【kmp算法next数组应用】Simpsons’ Hidden Talents HDU - 2594

Dear 丶 2022-06-07 02:41 209阅读 0赞

Think:  
1知识点：kmp算法next数组应用  
2题意：输入两个串，询问“最长前后缀”，“最长前后缀”定义为：串ans为st1的前缀，st2的后缀，输出“最长前后缀”和“最长前后缀”的长度  
3解题思路：连接串st1和st2，求next数组，next\[len-1\]表示串st的最大公共前后缀，需要判断len与len\_st1和len\_st2的长度，若len > len\_st1 或 len > len\_st2，则len = next\[len-1\];  
4反思：  
（1）：next数组开小了  
（2）：strcar(st1, st2)函数拼接串st1和串st2时要求st1数组的内存存储空间可以存储长度为len\_st1+len\_st2的串;  
![——截图来自百度百科][SouthEast]

以下为Time Limit Exceeded代码——next数组开小了以及st1数组开小了

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int max_size = 50414;
    
    int _next[max_size];
    char st1[max_size], st2[max_size];
    
    void get_next(char *P, int len_P);
    
    int main(){
        while(~scanf("%s %s", st1, st2)){
            int len1 = strlen(st1);
            int len2 = strlen(st2);
            strcat(st1, st2);
            int len = len1 + len2;
    
            get_next(st1, len);
            int cir_len = _next[len-1];
            while(cir_len > len1 || cir_len > len2){
                cir_len = _next[cir_len-1];
            }
    
            for(int i = 0; i < cir_len ; i++)
                printf("%c", st1[i]);
            if(cir_len) printf(" ");
            printf("%d\n", 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;
        }
        return;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int size_T = 50414;
    const int size_P = size_T << 1;
    
    int _next[size_P];
    char st1[size_P], st2[size_T];
    
    void get_next(char *P, int len_P);
    
    int main(){
        while(~scanf("%s %s", st1, st2)){
            int len1 = strlen(st1);
            int len2 = strlen(st2);
            strcat(st1, st2);
            int len = len1 + len2;
    
            get_next(st1, len);
            int cir_len = _next[len-1];
            while(cir_len > len1 || cir_len > len2){
                cir_len = _next[cir_len-1];
            }
    
            for(int i = 0; i < cir_len ; i++)
                printf("%c", st1[i]);
            if(cir_len) printf(" ");
            printf("%d\n", 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;
        }
        return;
    }

[SouthEast]: /images/20220607/740a3a2a4b3f4bf69e523c7d97bfa604.png