【kmp】Corporate Identity HDU - 2328

ゝ一纸荒年。 2022-06-07 05:19 161阅读 0赞

Think:  
1知识点：kmp算法+暴力枚举  
2题意：输入一组字符串，寻找最长公共子串，长度相同时选择字典序最小的  
3解题思路：  
（1）：找到字符串组中长度最短的字符串，然后根据左右区间枚举查询  
（2）：找到字符串组中长度最短的字符串，然后根据长度从大至小枚举，若在当前长度梯度已经找到串，则结束枚举（因为从大至小枚举的长度梯度级，因此下面枚举的长度梯度级要小于当前已经枚举完成的长度梯度级）  
4反思：  
（1）：len数组记录的是字符串组数，定义时应大于临界字符串组数(4000)，定义时定义的是至少大于临界最长字符串长度(200)，导致数组越界  
（2）：字符串数组’\\0’位置，混淆变量导致放置位置错误

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——字符串数组’\\0’位置，混淆变量导致放置位置错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 244;
    
    int _next[max_size], len[max_size];
    char st[4014][max_size], st1[max_size], st2[max_size], st3[max_size];
    
    void get_next(char *P, int len_P);
    bool kmp(char *T, int len_T, char *P, int len_P);
    
    int main(){
        int n, i, j, k, tmp, t;
        while(~scanf("%d", &n) && n){
            tmp = inf;
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                len[i] = strlen(st[i]);
                if(len[i] < tmp){
                    tmp = len[i], t = i;
                }
            }
            strcpy(st1, st[t]);
    
            int ans = 0;
            for(i = 0; i < tmp; i++){
                for(j = i; j < tmp; j++){
                    if(j-i+1 < ans) continue;
                    t = 0;
                    for(k = i; k <= j; k++){
                        st2[t++] = st1[k];
                    }
                    st2[k] = '\0';
                    for(k = 0; k < n; k++){
                        if(!kmp(st[k], len[k], st2, j-i+1)){
                            break;
                        }
                    }
                    if(k < n)
                        continue;
    
                    if(j-i+1 > ans){
                        strcpy(st3, st2);
                        ans = j-i+1;
                    }
                    else {
                        if(strcmp(st2, st3) < 0){
                            strcpy(st3, st2);
                            ans = j-i+1;
                        }
                    }
                }
            }
            if(ans) printf("%s\n", st3);
            else printf("IDENTITY LOST\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[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
        return;
    }
    bool kmp(char *T, int len_T, char *P, int len_P){
        int k, i;
        get_next(P, len_P);
        k = 0;
        for(i = 0; i < len_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == len_P) return true;
        }
        return false;
    }

以下为Wrong Answer代码——数组越界-提示Wrong Answer错误-why???

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 244;
    
    int _next[max_size], len[max_size];
    char st[4014][max_size], st1[max_size], st2[max_size], st3[max_size];
    
    void get_next(char *P, int len_P);
    bool kmp(char *T, int len_T, char *P, int len_P);
    
    int main(){
        int n, i, j, k, tmp, t;
        while(~scanf("%d", &n) && n){
            tmp = inf;
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                len[i] = strlen(st[i]);
                if(len[i] < tmp){
                    tmp = len[i], t = i;
                }
            }
            strcpy(st1, st[t]);
    
            int ans = 0;
            for(i = 0; i < tmp; i++){
                for(j = i; j < tmp; j++){
                    if(j-i+1 < ans) continue;
                    t = 0;
                    for(k = i; k <= j; k++){
                        st2[t++] = st1[k];
                    }
                    st2[t] = '\0';
    
                    for(k = 0; k < n; k++){
                        if(!kmp(st[k], len[k], st2, j-i+1))
                            break;
                    }
                    if(k != n)
                        continue;
    
                    if(j-i+1 > ans || !ans){
                        strcpy(st3, st2);
                        ans = j-i+1;
                    }
                    else {
                        if(strcmp(st2, st3) < 0){
                            strcpy(st3, st2);
                            ans = j-i+1;
                        }
                    }
                }
            }
            if(ans) printf("%s\n", st3);
            else printf("IDENTITY LOST\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[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
        return;
    }
    bool kmp(char *T, int len_T, char *P, int len_P){
        int k, i;
        get_next(P, len_P);
        k = 0;
        for(i = 0; i < len_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == len_P) return true;
        }
        return false;
    }

以下为Accepted代码——解题思路（1）

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 244;
    
    int _next[max_size], len[4014];
    char st[4014][max_size], st1[max_size], st2[max_size], st3[max_size];
    
    void get_next(char *P, int len_P);
    bool kmp(char *T, int len_T, char *P, int len_P);
    
    int main(){
        int n, i, j, k, tmp, t;
        while(~scanf("%d", &n) && n){
            tmp = inf;
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                len[i] = strlen(st[i]);
                if(len[i] < tmp){
                    tmp = len[i], t = i;
                }
            }
            strcpy(st1, st[t]);
    
            int ans = 0;
            for(i = 0; i < tmp; i++){
                for(j = i; j < tmp; j++){
                    if(j-i+1 < ans) continue;
                    t = 0;
                    for(k = i; k <= j; k++){
                        st2[t++] = st1[k];
                    }
                    st2[t] = '\0';
    
                    for(k = 0; k < n; k++){
                        if(!kmp(st[k], len[k], st2, j-i+1))
                            break;
                    }
                    if(k != n)
                        continue;
    
                    if(j-i+1 > ans || !ans){
                        strcpy(st3, st2);
                        ans = j-i+1;
                    }
                    else {
                        if(strcmp(st2, st3) < 0){
                            strcpy(st3, st2);
                            ans = j-i+1;
                        }
                    }
                }
            }
            if(ans) printf("%s\n", st3);
            else printf("IDENTITY LOST\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[q] != P[k]){
                k = _next[k-1];
            }
            if(P[q] == P[k])
                k++;
            _next[q] = k;
        }
        return;
    }
    bool kmp(char *T, int len_T, char *P, int len_P){
        int k, i;
        get_next(P, len_P);
        k = 0;
        for(i = 0; i < len_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == len_P) return true;
        }
        return false;
    }

以下为Accepted代码——解题思路（2）

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 204;
    
    int _next[max_size], len[4014];
    char st[4004][max_size], st1[max_size], ans[max_size];
    
    void get_next(char *P, int len_P);
    bool kmp(char *T, int len_T, char *P, int len_P);
    
    int main(){
        int n, i, j, k, len1, id;
        while(~scanf("%d", &n) && n){
            id = 0, len1 = inf;
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                len[i] = strlen(st[i]);
                if(len[i] < len1){
                    len1 = len[i], id = i;
                }
            }
    
            bool flag = false;
            for(i = len1; i >= 1 && !flag; i--){
                for(j = 0; j+i <= len1; j++){
                    for(k = 0; k < i; k++){
                        st1[k] = st[id][k+j];
                    }
                    st1[i] = '\0';
    
                    get_next(st1, i);
                    for(k = 0; k < n; k++){
                        int len_T = strlen(st[k]);
                        if(kmp(st[k], len_T, st1, i) == false)
                            break;
                    }
    
                    if(k == n){
                        if(!flag){
                            strcpy(ans, st1);
                            flag = true;
                        }
                        else if(flag && strcmp(st1, ans) < 0){
                            strcpy(ans, st1);
                        }
                    }
                }
            }
            if(flag) puts(ans);
            else puts("IDENTITY LOST");
        }
        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;
    }
    bool kmp(char *T, int len_T, char *P, int len_P){
        int k, i;
    
        k = 0;
        for(i = 0; i < len_T; i++){
            while(k > 0 && P[k] != T[i]){
                k = _next[k-1];
            }
            if(P[k] == T[i])
                k++;
            if(k == len_P) return true;
        }
        return false;
    }

[vjudge]: https://vjudge.net/problem/HDU-2328