2017青岛赛区亚洲区域赛网络赛 The Dominator of Strings

墨蓝 2022-06-08 06:52 221阅读 0赞

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

题意：问输入的串中是否存在一个串 包含其他所有串 有的话输出此串 没有的话输出No

思路：找出最长的串，然后其他串与它比较，看是否符合要求。

这是一开始的做法，用G++交就超时，赛后用C++交就能通过，可能是string的find函数效率太低？

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <string>
    #include <stack>
    #include <set>
    #define LL long long
    #define INF 0x7fffffff
    #define MAX 200010
    #define PI 3.1415926535897932
    #define E 2.718281828459045
    using namespace std;
    set<string>s;
    int t,n;
    string ss,st;
    int main()
    {
        int len;
        scanf("%d",&t);
        while(t--){
            len=0;
            s.clear();
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                cin>>ss;
                s.insert(ss);
                if(len<ss.size()){
                    len=ss.size();
                    st=ss;
                }
            }
            set<string>::iterator it;
            bool flag=true;
            for(it=s.begin();it!=s.end();it++){
                if(st.find(*it)==-1){
                    //cout<<*it<<endl;
                    flag=false;
                    break;
                }
            }
            if(flag) cout<<st<<endl;
            else printf("No\n");
        }
        return 0;
    }

于是从网上搜了一下别人的做法，找到了一个题解，他的做法和我一样，只是将find函数换了一下，用C++交对，但是用G++交还是超时，很纳闷

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<vector>
    using namespace std;
    
    typedef long long int LL;
    
    int Sunday(string text, string pattern)  //如果pattern串不是text的子串返回-1  是的话返回在text串的开始下标(从0开始)
    {
        int i = 0, j = 0, k;
        int m = pattern.size();
        if(pattern.size() <= 0 || text.size() <= 0)
            return -1;
    
        for(; i<text.size();)
        {
            if(text[i] != pattern[j])
            {
                for(k=pattern.size() - 1; k>=0; k--)
                {
                    if(pattern[k] == text[m])
                        break;
                }
                i = m-k;
                j = 0;
                m = i+pattern.size();
            }
            else
            {
                if(j == pattern.size()-1)
                    return i-j;
                i++;
                j++;
            }
        }
        return -1;
    }
    
    vector<string> v;
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            v.clear();
            string t,text;
            for(int i=0; i<n; i++)
            {
                cin>>t;
                if(text.length()<t.length())
                    text=t;
                v.push_back(t);
            }
            int f=1;
            for(int i=0; i<n; i++)
            {
                if(Sunday(text,v[i])== -1)
                {
                    f=0;
                    break;
                }
            }
            if(f)  cout<<text<<endl;
            else   cout<<"No"<<endl;
        }
        return 0;
    }
     
    
     
     
     
      
      
       
    
     
      
     
      
      
       
    
     
      
     
      
      
       于是我又用了KMP算法来试试，结果还是用C++交就对了，用G++就不对，/(ㄒoㄒ)/~~
     
      
     
      
      
       #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<string.h>
    using namespace std;
    typedef long long int LL;
    const int N = 1000002;
    string t,text;
    int slen,tlen;
    int nexts[N];
    
    void getNext(string T)
    {
        int j, k;
        j = 0; k = -1; nexts[0] = -1;
        while(j < tlen)
            if(k == -1 || T[j] == T[k])
                nexts[++j] = ++k;
            else
                k = nexts[k];
    
    }
    
    int KMP_Index(string S,string T)  //KMP模板 next数组从1开始
    {
        int i = 0, j = 0;
        getNext(T);
        while(i < slen && j < tlen)
        {
            if(j == -1 || S[i] == T[j])
            {
                i++; j++;
            }
            else
                j = nexts[j];
        }
        if(j == tlen)
            return i - tlen;
        else
            return -1;
    }
    vector<string> v;
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            v.clear();
            text="";
            for(int i=0; i<n; i++)
            {
                cin>>t;
                if(text.length()<t.length())
                    text=t;
                v.push_back(t);
            }
            int f=1;
            slen=0,tlen=0;
            for(int i=0; i<n; i++)
            {
                slen=text.size();
                tlen=v[i].size();
                if(KMP_Index(text,v[i])== -1)
                {
                    f=0;
                    break;
                }
            }
            if(f)  cout<<text<<endl;
            else   cout<<"No"<<endl;
        }
        return 0;
    }