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
- 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[110];
- vector<string> t;
- void prekmp(string s) {
- int len=s.size();
- int i,j;
- j=Next[0]=-1;
- i=0;
- while(i<len) {
- while(j!=-1&&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=0,j=0,ans=-1,res;
- res=-1;
- while(i<lent) {
- while(j!=-1&&t[i]!=p[j]) j=Next[j];
- ++i;++j;
- res=max(res,j);
- }
- ans=max(ans,res);
- reverse(t.begin(),t.end());
- res=-1;
- i=0,j=0;
- while(i<lent) {
- while(j!=-1&&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=0;i<n;i++) {
- cin>>s;
- t.push_back(s);
- }
- string str=t[0],tempstr;
- int len=str.size(),maxx=-1;
- for(int i=0;i<len;i++) {
- tempstr=str.substr(i,len-i);
- int ans=0x3f3f3f;
- prekmp(tempstr);
- for(int j=1;j<t.size();j++) {
- ans=min(kmp(t[j],tempstr),ans);
- }
- maxx=max(maxx,ans);
- }
- printf("%d\n",maxx);
- t.clear();
- }
- }
来源: http://www.bubuko.com/infodetail-2929070.html