【kmp算法】Substrings HDU - 1238

末蓝、 2022-06-07 05:10 176阅读 0赞

Think:  
1知识点：kmp算法  
2题意：T组测试数据，每组测试数据输入n个字符串，询问最长长度的子串x，要求子串x或者子串x的翻转串在每个字符串中都会出现  
3思路：找到最小的字符串，然后暴力枚举子串查询，剪枝优化  
4反思：  
（1）：字符串长度为1的字符串不要忘记

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——未枚举字符串长度为1的字符串

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 144;
    
    int _next[max_size], len[max_size];
    char st[104][max_size], st1[max_size], st2[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 T, n, i, j, k, tmp, t;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &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+1; j < tmp; j++){
                    if(j-i+1 <= ans) continue;
                    t = 0;
                    for(k = j; k >= i; k--){
                        st2[t++] = st1[k];
                    }
                    for(k = 0; k < n; k++){
                        if(!kmp(st[k], len[k], &st1[i], j-i+1) && !kmp(st[k], len[k], st2, j-i+1))
                            break;
                    }
                    if(k == n) ans = j-i+1;
                }
            }
            printf("%d\n", ans);
        }
        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代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int max_size = 144;
    
    int _next[max_size], len[max_size];
    char st[104][max_size], st1[max_size], st2[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 T, n, i, j, k, tmp, t;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &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 = j; k >= i; k--){
                        st2[t++] = st1[k];
                    }
                    for(k = 0; k < n; k++){
                        if(!kmp(st[k], len[k], &st1[i], j-i+1) && !kmp(st[k], len[k], st2, j-i+1))
                            break;
                    }
                    if(k == n) ans = j-i+1;
                }
            }
            printf("%d\n", ans);
        }
        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;
    }

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