题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6208
Problem Description
Here 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.
Input
The 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.
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.
Output
For 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 aaaac
Sample Output
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness abcde No
用了string里面的比较函数find函数,可以查一下
代码如下:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define da 10000000
#define xiao -10000000
#define clean(a,b) memset(a,b,sizeof(a))
string chuan[100000]; //类似二位字符串数组
string str; //
int l[100000]; //
int main()
{
ios::sync_with_stdio(0); //加快cin的输入速度
int t;
scanf("%d",&t);
while(t--)
{
int f=1;
clean(l,0);
int n,max=0,maxi,i;
scanf("%d",&n);
for(i=0;i<n;++i) //清空
chuan[i].clear();
for(i=0;i<n;++i) //输入 n个字符串
cin>>chuan[i];
str=chuan[0]; //让参数等于第一个字符串
for(i=0;i<n;++i) //对比每个字符串
{
if(chuan[i].length()>str.length()) //判断长度
str=chuan[i]; //长的那个为母串;
}
for(i=0;i<n;++i) //遍历所有的字符串
{
if(str.find(chuan[i])==str.npos) //如果有一个不包含 这个find函数就是判断函数有没有包含
{
f=0; //结束循环
break;
}
}
if(f)
cout<<str<<endl; //有则输出
else
printf("No\n"); //无则no;
}
}