【KMP算法】The Dominator of Strings HDU - 6208

你的名字 2022-06-08 06:50 114阅读 0赞

Think:  
1题意：输入串的集合，判断是否存在一个串，使得集合内其它的串为这个串的子串，如果存在则输出这个串，否则输出No;  
2思路：找到一个长度最长的串，其它串的长度小于等于这个串，然后多次KMP匹配  
3注意：  
（1）每组测试数据的总长度不超过100000，即N和len的长度都可能达到100000，因此无法直接通过二维char数组存储，需要通过string存储  
（2）输入数据量较大，建议使用scanf读入char类型一维数组然后将其赋值给string类型的变量(string类型变量初始化)

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    char st[101400];
    string str[101400];
    
    int _next[101400];
    void get_next(string P);
    bool kmp(string T, string P);
    
    int main(){
        int T, n, i, mav, v, len;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            getchar();
            for(i = 0; i < n; i++){
                scanf("%s", st);
                str[i] = st;
            }
            mav = 0;
            for(i = 0; i < n; i++){
                len = str[i].size();
                if(len > mav){
                    mav = len, v = i;
                }
            }
    
            bool flag = true;
            for(i = 0; i < n; i++){
                if(i != v && !kmp(str[v], str[i])){
                    flag = false;
                    break;
                }
            }
            if(flag) cout << str[v] << endl;
            else printf("No\n");
        }
        return 0;
    }
    void get_next(string P){
        int k, q, len_P = P.size();
        _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;
        }
    }
    bool kmp(string T, string P){
        int q, i;
        int len_T = T.size();
        int len_P = P.size();
        get_next(P);
        q = 0;
        for(i = 0; i < len_T; i++){
            while(q > 0 && T[i] != P[q]){
                q = _next[q-1];
            }
            if(T[i] == P[q]){
                q++;
                if(q == len_P)
                    return true;
            }
        }
        return false;
    }

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