2013
12-04

# Substrings

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.

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.

There should be one line per test case containing the length of the largest string found.

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

2
2

http://acm.hdu.edu.cn/showproblem.php?pid=1238

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n;
string s[111];

int cmp(const string p,const string q){
return p.length()<q.length();
}

int dfs(string &str){
int len=str.length();
int flag=1;
for(int i=len;i>=1;i--){
for(int j=0;i+j<=len;j++){
string temp=str.substr(j,i);
string t=temp;
string retemp=t.assign(t.rbegin(),t.rend());
for(int k=1;k<n;k++){
if(s[k].find(temp)==-1&&s[k].find(retemp)==-1){
flag=0;
break;
}
}
if(flag)return temp.length();
flag=1;
}
}
return 0;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n,cmp);
int ans=dfs(s[0]);
printf("%d\n",ans);
}
return 0;
}