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; }