Substrings
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 12072 | Accepted: 4233 |
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 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.
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
22
/* 用到了KMP算法 解法很一般，先对字符串排个序，最短的在最前面。 然后通过枚举（从长到短）每一个最短串的子串，看其或其反串是否是其他所有串的子串。 */ #include<stdio.h> #include<string>//注意不是string.h,WA了好几次 #include<iostream> #include<algorithm> using namespace std; int mFlags, nFlags, pString[101];//mFlags是最短字符串长度,nFlags是待比较字符串长度 //比较字符串长度 bool Compare_str(string s1,string s2){ return s1.length()<s2.length(); } //字符串匹配 int KMP(string a,string b){ pString[0] = -1; int i,j = -1; for(i=1; i<mFlags; i++){ if(j>-1 && b[j+1] != b[i]) j = pString[j]; if(b[j+1] == b[i]) j += 1; pString[i] = j; } j = -1; for(i=0; i<nFlags; i++){ if(j>-1 && b[j+1] != a[i]) j = pString[j]; if(b[j+1] == a[i]) j += 1; if(j == mFlags-1){ return 1; j = pString[j]; } } return 0; } int main(){ int times,lines; string sString[101]; cin >> times; while(times--){ cin >> lines; for(int i=0; i<lines; i++) cin >> sString[i]; //从小到大将字符串排序 sort(sString, sString+lines, Compare_str); string aStr,bStr; //得到第一个字符串(最小)的长度 int len = sString[0].length(); int flag = 0; //遍历比较所有字符串 for(int i=len; i>0; i--){ for(int j=0; j<=len-i; j++){ aStr = sString[0].substr(j,i); bStr = aStr; //将字符串反转 reverse(bStr.begin(), bStr.end()); mFlags = aStr.length(); int k; for(k=1; k<lines; k++){ nFlags = sString[k].length(); if(!(KMP(sString[k], aStr)||KMP(sString[k], bStr))) break; } //到达最后一行字符串则跳出 if(k == lines){ flag = 1;//设置标志 break; } } if(flag) break; } if(flag) cout << aStr.length() << endl; else cout << 0 << endl; } return 0; }