You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
找出最长的一个子串,所有串中都出现过它或它的逆序
扩展KMP水题
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std; const int maxn=;
int nxt[][maxn],ext[][maxn];
char s[][maxn];
int len[],ans[maxn]; void EKMP(char s[],char t[],int lens,int lent,int c){
int i,j,p,l,k;
nxt[c][]=lent;j=;
while(j+<lent&&t[j]==t[j+])j++;
nxt[c][]=j;
k=;
for(i=;i<lent;i++){
p=nxt[c][k]+k-;
l=nxt[c][i-k];
if(i+l<p+)nxt[c][i]=l;
else{
j=max(,p-i+);
while(i+j<lent&&t[i+j]==t[j])j++;
nxt[c][i]=j;
k=i;
}
} j=;
while(j<lens&&j<lent&&s[j]==t[j])j++;
ext[c][]=j;k=;
for(i=;i<lens;i++){
p=ext[c][k]+k-;
l=nxt[c][i-k];
if(l+i<p+)ext[c][i]=l;
else{
j=max(,p-i+);
while(i+j<lens&&j<lent&&s[i+j]==t[j])j++;
ext[c][i]=j;
k=i;
}
}
} int main(){
int T;
scanf("%d",&T);
while(T--){
memset(ans,0x3f,sizeof(ans));
int n;
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%s",s[i]);
for(int i=;i<=n;++i)len[i]=strlen(s[i]);
s[][len[]]='#';
for(int i=;i<=len[];++i)s[][len[]+i]=s[][len[]-i];
s[][len[]+len[]+]=;
len[]=strlen(s[]);
int maxx=;
for(int i=;i<len[];++i){
for(int j=;j<=n;++j){
int cnt=;
EKMP(s[j],s[]+i,len[j],len[]-i,j);
for(int k=;k<len[j];++k){
if(ext[j][k]>cnt)cnt=ext[j][k];
}
if(cnt<ans[i])ans[i]=cnt;
}
if(ans[i]>maxx)maxx=ans[i];
}
printf("%d\n",maxx);
}
return ;
}