思路
直接暴力枚举第一个字符串所有的切割情况，然后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;
}
