题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6208
Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string SS is dominated by TT if SS is a substring of TT.
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 NN indicating the size of the set.
Each of the following NN lines describes a string of the set in lowercase.
The total length of strings in each case has the limit of 100000100000.
The limit is 30MB for the input file.OutputFor each test case, output a dominator if exist, or No if not.Sample Input
3 10 you better worse richer poorer sickness health death faithfulness youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness 5 abc cde abcde abcde bcde 3 aaaaa aaaab aaaacSample Output
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness abcde No
题目大意:t次,n个字符串,从中找到一个母串,母串里面包含着其他的字串,输出母串,否则输出no
用到一个函数,就是发现函数,在c++中的string:
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define da 0x3f3f3f3f
#define xiao -0x3f3f3f3f
#define clean(a,b) memset(a,b,sizeof(a))// 雷打不动的头文件
string chuan[1000000];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,max=xiao,maxi;
cin>>n;
int i,j;
for(i=0;i<n;++i)
chuan[i].clear();
for(i=0;i<n;++i)
cin>>chuan[i];
string str;
str=chuan[0];
for(i=0;i<n;++i)
{
if(chuan[i].length()>str.length())
str=chuan[i]; //找到最长的一个母串
}
int f=1;
for(i=0;i<n;++i)
{
if(str.find(chuan[i])==str.npos)
{
f=0; //只要有一个不符合就
break;
}
}
if(f)
cout<<str<<endl; //输出对应的 母串
else
cout<<"No"<<endl;
}
}