Problem Description
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.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2 3 ABCD BCDFF BRCD 2 rose orchid
Sample Output
2 2
直接暴力kmp即可
有一个函数 ：reverse(p2.begin(),p2.end()); 可以直接反转
注意如果没有则输出0；
第一次的写法 虽然艰难的过了 但是时间为500ms
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define inf 0x3f3f3f3f
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 100+5
#define mod 10007
string s,p;
int can[];
string temp[N];
int nex[N];
string str;
int lenp,lens;
void getnext()
{
nex[]=-;
int k=-,j=;
while(j<lenp-)
{
if(k==-||p[k]==p[j])
nex[++j]=++k;
else k=nex[k];
}
}
int kmp(string s)
{
int lens=s.size();
int j=,i=;
while(i<lens&&j<lenp)
{
if(s[i]==p[j]||j==-)
{
i++;
j++;
}
else j=nex[j];
if(j==lenp)
{
return ;
}
}
return ;
}
int main()
{ int cas;
RI(cas);
while(cas--)
{
int n;RI(n);
int minn=inf;
rep(i,,n)
{
cin>>temp[i];
if(temp[i].size()<minn )minn=temp[i].size();
}
rep(i,,n)
if(temp[i].size()==minn)
{
str=temp[i];
break;
}
int end1=;
int maxx=;
for(lenp=minn;lenp>=;lenp--)
{
if(end1)break;
for(int j=;j<=minn;j++)
if(j+lenp-<minn)
{
int ok=;
p=str.substr(j,lenp);
getnext();
rep(i,,n)
{
can[i]=; if(kmp(temp[i]))
can[i]=;
}
reverse(p.begin(),p.end());
getnext();
rep(i,,n)
{ if(kmp(temp[i]))
can[i]=; if(can[i]==)
{
ok=;break;
}
}
if(ok)
{
maxx=lenp;end1=;
break;
}
}
}
cout<<maxx<<endl;
}
return ;
}
下面的为70ms
因为其实大部分情况下是不匹配的 匹配的情况微乎其微 所以直接两个一起判断即可 即使每次判断都要更行next
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define inf 0x3f3f3f3f
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 100+5
#define mod 10007
string s,p;
int can[];
string temp[N];
int nex[N];
string str;
int lenp,lens;
void getnext()
{
nex[]=-;
int k=-,j=;
while(j<lenp-)
{
if(k==-||p[k]==p[j])
nex[++j]=++k;
else k=nex[k];
}
}
int kmp(string s)
{
int lens=s.size();
int j=,i=;
while(i<lens&&j<lenp)
{
if(s[i]==p[j]||j==-)
{
i++;
j++;
}
else j=nex[j];
if(j==lenp)
{
return ;
}
}
return ;
}
int main()
{
int cas;
RI(cas);
while(cas--)
{
int n;RI(n);
int minn=inf;
rep(i,,n)
{
cin>>temp[i];
if(temp[i].size()<minn )minn=temp[i].size();
}
rep(i,,n)
if(temp[i].size()==minn)
{
str=temp[i];
break;
}
int maxx=;
int end1=;
for(lenp=minn;lenp>=;lenp--)
{
if(end1)break;
for(int j=;j<=minn;j++)
if(j+lenp-<minn)
{
string p1=str.substr(j,lenp);
string p2=p1;
reverse(p2.begin(),p2.end()); int i;
for(i=;i<=n;i++)
{
int flag=;
p=p1;
getnext();
if(kmp(temp[i]))
flag=;
p=p2;
getnext();
if(kmp(temp[i]))
flag=;
if(flag==)
break;
}
if(i==n+&&maxx<lenp)
maxx=lenp,end1=;
}
}
cout<<maxx<<endl;
}
return ;
}