Substrings

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10145    Accepted Submission(s): 4820 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   Author Asia 2002, Tehran (Iran), Preliminary

题意：给我们n个字符串，问我们其中最长公共子序列(包括反序列)长度是多少。

分析：为了简化步骤，我们在输入n个字符串后，取其中最短的一个串作为原模式串，与其它串进行匹配。匹配使用的模式串由这个原模式串 枚举首尾下标获得。获得par串后对多个ori串KMP，更新结果值。我存储多个字符串用的是二维数组，也可以写结构体或者string。下面是Doge加强注释and变量名的AC代码：

#include <bits/stdc++.h> using namespace std; const int MAXN=110; char ori[MAXN][MAXN],par[MAXN],parB[MAXN]; int nex[MAXN]; int minStrLen,minStrLenID; void preKMP(char s[],int n[]) { int p=0,q=-1; n[0]=-1; while(s[p]){ while(q!=-1 && s[q]!=s[p]) q=n[q]; n[++p]=++q; } } bool KMP(char a[],char b[]) { int p=0,q=0,l=strlen(a); preKMP(a,nex); while(b[p]){ while(q!=-1 && a[q]!=b[p]) q=nex[q]; ++p; ++q; if(q>=l) return true; } return false; } int main() { int t,n; for(scanf("%d",&t);t;t--) { scanf("%d",&n); minStrLen=2017; for(int i=0;i<n;i++) { scanf("%s",ori[i]); //读入所有串并找出最短串位置 int len=strlen(ori[i]); if(len<minStrLen) { minStrLen=len; minStrLenID=i; } } int ans=0; //最长公共子序列长度初始化 for(int i=0;i<minStrLen;i++) //前端向后枚举 { // 枚举出模式串起点终点 for(int j=minStrLen-1;j>=i;j--) //尾端向前枚举 { int parLen=0; for(int k=i;k<=j;k++) par[parLen++]=ori[minStrLenID][k]; par[parLen]='\0'; //完成顺序串构造 int parLenB=0; for(int k=j;k>=i;k--) parB[parLenB++]=ori[minStrLenID][k]; parB[parLenB]='\0'; //完成逆序串构造 bool match=true; for(int k=0;k<n;k++) //开始检测所有串匹配度 { if(!KMP(par,ori[k]) && !KMP(parB,ori[k])) { match=false; //一旦某一个都不能匹配两个串之一 break; //就不具有公共性 } } if(match) //如果par串能匹配所有串 { ans=max(ans,j-i+1); //视情况更新ans值 break; //跳出j循环，后面的情况得到的j-i+1只会更小 } } } printf("%d\n",ans); } return 0; }

这题数据很弱，我们可以用String来一发暴力。（喂ヽ(●-`Д´-)ノKMP也算暴力过的）

#include <iostream> #include <algorithm> #include <string> using namespace std; string str[101]; int cmp (const string str1, const string str2) { return (str1.length() < str2.length()); } int main() { int t, n, result; string strc, strr; int i, j, k; cin >> t; while (t-- && cin >> n) { result = 0; for (i = 0; i < n; i++) { cin >> str[i]; } sort (str, str+n, cmp);//按长度排序所有字符串 for (i = 0; i < str[0].length(); i++) for (j = 0; j+i <= str[0].length(); j++) { strc = str[0].substr(i, j);//求子字符串 strr.assign(strc.rbegin(), strc.rend());//求逆向子字符串 for (k = 1; k < n; k++) { if (str[k].find(strc) == string::npos && str[k].find(strr) == string::npos) break;//没有找到匹配的子字符串 } if (k == n && strc.length() > result)//找到了子字符串&&长度比之前都大 result = strc.length();//保存 } cout << result << endl; } return 0; }