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.
InputThe 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.
OutputThere should be one line per test case containing the length of the largest string found.
Sample Input
(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.
OutputThere 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 这道题和之前一道题类似，都是多个字符串匹配问题，只是这道题多了倒序的匹配。直接reverse就可以了
遍历第一个串的所有后缀，然后匹配每个字符串的正反序。得到公共匹配的最小。然后枚举所有后缀取最大
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int _,n,Next[];
vector<string> t; void prekmp(string s) {
int len=s.size();
int i,j;
j=Next[]=-;
i=;
while(i<len) {
while(j!=-&&s[i]!=s[j]) j=Next[j];
Next[++i]=++j;
}
} int kmp(string t,string p) {
int lent=t.size(),lenp=p.size();
int i=,j=,ans=-,res;
res=-;
while(i<lent) {
while(j!=-&&t[i]!=p[j]) j=Next[j];
++i;++j;
res=max(res,j);
}
ans=max(ans,res);
reverse(t.begin(),t.end());
res=-;
i=,j=;
while(i<lent) {
while(j!=-&&t[i]!=p[j]) j=Next[j];
++i;++j;
res=max(res,j);
}
ans=max(ans,res);
return ans;
} int main() {
// freopen("in","r",stdin);
for(scanf("%d",&_);_;_--) {
scanf("%d",&n);
string s;
for(int i=;i<n;i++) {
cin>>s;
t.push_back(s);
}
string str=t[],tempstr;
int len=str.size(),maxx=-;
for(int i=;i<len;i++) {
tempstr=str.substr(i,len-i);
int ans=0x3f3f3f;
prekmp(tempstr);
for(int j=;j<t.size();j++) {
ans=min(kmp(t[j],tempstr),ans);
}
maxx=max(maxx,ans);
}
printf("%d\n",maxx);
t.clear();
}
}