HDU - 6208 The Dominator of Strings (2017 ACM-ICPC 亚洲区 (青岛赛区) 网络赛 1003)-CSDN博客

2017 ACM/ICPC Asia Regional Qingdao Online 1003

The Dominator of Strings

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

题意：很简单……求小的串是否在最大的串内

解题思路：胜利属于JAVA……JAVA暴力加contains函数就过了……但是貌似所有人都超时了……这里要用bufferedreader去读取……才能不超时……而且还贼快！

import java.io.*;
public class Main {
    static String str[]=new String[100010];
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String t=bf.readLine();
        int T=Integer.parseInt(t);
        while(T>0){
            String nr=bf.readLine();
            int n;
            n=Integer.parseInt(nr);
            String fstr="";
            for(int i=0;i<n;i++){
                str[i]=bf.readLine();
                if(str[i].length()>fstr.length()) fstr=str[i];    
            }
            int flag=1;
            for(int i=0;i<n;i++){
                if(!fstr.contains(str[i])){
                    flag=0;break;
                }
            }
            if(flag==1) System.out.println(fstr);
            else System.out.println("No");
            T--;
        }
    }
}