首页 > 代码库 > POJ 1226 Substrings
POJ 1226 Substrings
Substrings
Time Limit: 1000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 122664-bit integer IO format: %lld Java class name: Main
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.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
23ABCDBCDFFBRCD2roseorchid
Sample Output
22
Source
Tehran 2002 Preliminary
解题：霸蛮好了。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 string str[110];18 int main() {19 int t,i,j,k,n;20 bool flag;21 scanf("%d",&t);22 while(t--){23 scanf("%d",&n);24 for(i = 0; i < n; i++)25 cin>>str[i];26 sort(str,str+n);27 flag = false;28 for(k = str[0].length(); k; k--){29 for(i = 0; i + k <= str[0].length(); i++){30 string a = str[0].substr(i,k);31 string b(a.rbegin(),a.rend());32 for(j = 1; j < n; j++)33 if(str[j].find(a) == -1 && str[j].find(b) == -1) break;34 if(j == n) {flag = true;break;}35 }36 if(flag) break;37 }38 flag?printf("%d\n",k):puts("0");39 }40 return 0;41 }
POJ 1226 Substrings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。