Substrings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 14485 Accepted Submission(s): 7090
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
Recommend Eddy
大致题意：给定一个数n，下面有n个字符串，求这n个字符串（或者逆序的字符串也可）中最长的公共字符字串。 思路：先排序，取最小的字符串来进行匹配（复杂度比较低），取该字符串的字串，从长取到短，对于取出来的每一个字串，若都在其他字符串或者他们的逆序串中出现过，直接输出当前长度。
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxn = 110; int ne[maxn]; bool cmp(const string a, const string b) { return a.size() < b.size(); } void getNext(string p) { int j, k; int len = p.size(); j = 0, k = -1; ne[0] = -1; while(j < len){ if(k == -1 || p[j] == p[k]){ j++; k++; ne[j] = ne[k]; } else k = ne[k]; } } int kmp(string p, string s) { int i,j; i = j = 0; int pLen, sLen; pLen = p.size(); sLen = s.size(); while(i < sLen && j < pLen){ if(j == -1 || s[i] == p[j]){ i++; j++; } else j = ne[j]; } if(j == pLen) return i - j; else return -1; } string s[maxn]; int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); for(int i = 0; i < n; i++){ cin>>s[i]; } sort(s, s + n, cmp);/*字符串短的在前*/ int len = s[0].size(); int i; for(i = len; i >= 0; i--){ for(int j = 0; j + i <= len; j++){ string subs = s[0].substr(j, i); // cout<<subs<<endl;/*取字串没有问题*/ getNext(subs); int k; for(k = 1; k < n; k++){ int ans = kmp(subs, s[k]); string s2 = ""; for(int m = 0; m < s[k].size(); m++) s2 = s[k][m] + s2; int ans2 = kmp(subs, s2); if(ans == -1 && ans2 == -1)break; } if(k == n)goto loop; } } loop: printf("%d\n", i); } return 0; } /* 2 3 ABCD BCDFF BRCD 2 rose orchid */