HDU 6208 The Dominator of Strings（stl）

The Dominator of Strings

Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2439 Accepted Submission(s): 879

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.

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

Source

2017 ACM/ICPC Asia Regional Qingdao Online

Recommend

liuyiding | We have carefully selected several similar problems for you: 6216 6215 6214 6213 6212

题解：

很水的一题，暴力就可以解决，直接取最长的作为模板串，如果和他等长的串和他不相同就不可以，然后其他的串要在那个串里面找得到。。。

比赛的时候我tm也是醉了，莫名其妙wa了好几遍，最后也没发现错，后来比完赛才知道错在了取消了cin和cout的同步以后用printf就会出错了。。。我把printf改成cout就ac了，我%@#￥@#￥@#￥@，以后不能随便用取消同步了

代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long
#define INF 100861111
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
struct node
{
    string s;
};
node p[100005];
string t;
int main()
{
    std::ios::sync_with_stdio(false);
    int test,i,j,n,num,maxx,tag;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        maxx=0;
        for(i=0;i<n;i++)
        {
            cin>>p[i].s;
            if(p[i].s.size()>maxx)
            {
                maxx=p[i].s.size();
                t=p[i].s;
            }
        }
        tag=1;
        for(i=0;i<n;i++)
        {
            if(p[i].s.size()==maxx)
            {
                if(p[i].s!=t)
                {
                    tag=0;
                    break;
                }
            }
            else
            {
                if(t.find(p[i].s)==string::npos)
                {
                    tag=0;
                    break;
                }
            }
        }
        if(tag)
            cout<<t<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}