[kuangbin带你飞]专题十六 KMP & 扩展KMP &

题目

思路

直接暴力枚举第一个字符串所有的切割情况，然后kmp挨个匹配

• 注意题目要求相同长度字典序排序

AC代码

#include<iostream>
using namespace std;
const int MAXN = 70;
int NEXT[MAXN];
string P;
string T;
string str[12];
int plen;
int tlen;
void getNEXT(){
    int k,j;
    tlen = T.length();
    plen = P.length();
    k = -1;j = 0;NEXT[0] = -1;
    while(j<plen){
        if(k==-1||P[k] == P[j]){
            NEXT[++j] = ++k; 
            if(P[j] == P[k]){
                NEXT[j] = NEXT[k];
            }
        }else{
            k=NEXT[k];
        }
    }
    
}

int main(){
    int TT;
    cin>>TT;
    int flag = false;
    while(TT--){
        flag = false;
        int N;
        string ans="";
        cin>>N;
        for(int i = 0 ; i< N ;i++){
            cin>>str[i];
            if(i==0){
                T=str[i];
            }
        }
        for(int len=60;len>=3;len--){
            for(int be=0;be+len<=60;be++){
                    string tempstr;
                    tempstr = str[0].substr(be,len);
//                  cout<<"P "<<tempstr<<endl;
                    if(tempstr == P)
                        continue;
                    P=tempstr;
                    bool flag1 = true;
                    for(int s = 1 ;s<N;s++){
                        T = str[s];
                        if(KMP_Index()==-1){
                            flag1 = false;
                        }
                    }
                    if(flag1 == true){
                        if(ans>P||ans=="")
                            ans = P;
                        flag=true;
                    }
            }       
            if(flag) break;
        }
        if(flag)    cout<<ans<<"\n";        
        else    cout<<"no significant commonalities\n";
    }   
    return 0;   
}