The Dominator of Strings
Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem DescriptionHere you have a set of strings. A dominator is a string of the set dominating all strings else. The string S is dominated by T if S is a substring of T. InputThe input contains several test cases and the first line provides the total number of cases.
For each test case, the first line contains an integer N indicating the size of the set.
Each of the following N lines describes a string of the set in lowercase.
The total length of strings in each case has the limit of 100000.
The limit is 30MB for the input file. OutputFor each test case, output a dominator if exist, or No if not. Sample Input3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac Sample Outputyoubemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
abcde
No Source输入输出测试
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std ;
vector<string> dic ;
string str ,tp ;
int main()
{
IO;
int t,n; cin >> t ;
while(t--)
{
int n , len = - , buf ;
cin >> n ;
dic.clear() ;
for(int i = ; i < n ; i++ )
{
cin >> tp ;
dic.push_back(tp) ;
int x = tp.length();
if( x > len )
{
len = x ;
str = tp ;
}
} bool flag = true ;
for( int i = ; i < n ; i++ )
{ if( str.find(dic[i]) == string::npos )
{
flag = false ;
break ;
}
}
if( flag )
{
cout << str << endl ;
}
else
{
cout << "No" <<endl ;
}
}
return ;
}