【kmp算法-子串暴力匹配+字符串地址传入】Blue Jeans POJ - 3080

傷城~ 2022-06-07 02:25 110阅读 0赞

Think:  
1知识点：kmp算法+子串暴力匹配  
2题意：输入n(2<=n<=10)个字符串集合(len == 60)，询问n个字符串的最长公共子串，若长度相同，则输出字典序最小的  
3解题思路：通过传入字符串地址和长度枚举第一个串的子串在其它串中是否可以匹配，更新维护最优解

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int max_size = 104;
    
    int _next[max_size];
    char st1[max_size], st[14][max_size];
    char link[max_size], que[max_size];
    
    void get_next(char *P, int len_P);
    bool kmp(char *P, int len_P, char *T, int len_T);
    
    int main(){
        int T, n, i, j, k, tmp, ans;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            scanf("%s", st1);
            for(i = 0; i < n-1; i++)
                scanf("%s", st[i]);
            int len_P = strlen(st1);
            ans = 0;
            for(i = 0; i < len_P; i++){
                for(j = i+1; j < len_P; j++){
                    tmp = j - i + 1;
                    if(tmp < ans) continue;
                    for(k = 0; k < n-1; k++){
                        int len_T = strlen(st[k]);
                        if(!kmp(&st1[i], tmp, st[k], len_T))
                            break;
                    }
                    if(k != n-1)
                        continue;
                    if(tmp > ans){
                        ans = tmp;
                        int tp = 0;
                        for(int t = i; t <= j; t++){
                            link[tp++] = st1[t];
                        }
                        link[tp] = '\0';
                    }
                    else {
                        int tq = 0;
                        for(int t = i; t <= j; t++){
                            que[tq++] = st1[t];
                        }
                        que[tq] = '\0';
                        if(strcmp(que, link) < 0)
                            strcpy(link, que);
                    }
                }
            }
            if(ans < 3) printf("no significant commonalities\n");
            else {
                printf("%s\n", link);
            }
        }
        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;
        }
        return;
    }
    bool kmp(char *P, int len_P, char *T, int len_T){
        /*for(int i = 0; i < len_P; i++)
            printf("%c", P[i]);
        printf("\n");*/
    
        int i, k;
        get_next(P, len_P);
        k = 0;
        for(i = 0; i < len_T; i++){
            while(k > 0 && T[i] != P[k]){
                k = _next[k-1];
            }
            if(T[i] == P[k])
                k++;
            if(k == len_P)
                return true;
        }
        return false;
    }

[vjudge]: https://vjudge.net/problem/POJ-3080