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
Each of the following N
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
【题意】：给n个串，问是否有一个串，包含了其他所有串。
【分析】：显然若这样的字符串存在就一定是最长的那个，然后考虑下AC自动机的入门题HDU2222，然后思路就清晰了，首先构建自动机，然后选出长度最长的一串来跑一遍自动机，统计所有字符串出现的个数，不重复统计，然后个数!=n就是No。
【代码*3】：
#include<stdio.h> #include<string.h> #include<queue> #include<string> #include<iostream> #define maxlen 100005 using namespace std; int n; int nxt[maxlen][30],FAIL[maxlen],edd[maxlen],root,L;//nxt记录节点，在这里edd指针代表以当前节点为字符串尾的字符串个数 int mark[maxlen]; int newnode() { for(int i=0;i<26;i++) nxt[L][i]=-1;//节点连接的边初始化为-1 edd[L]=0; mark[L]=0; return L++; } void init() { L=0; root=newnode(); } void insert(char buf[],int l)//trie树的建立 { int now=root; for(int i=0;i<l;i++) { if(nxt[now][buf[i]-'a']==-1)nxt[now][buf[i]-'a']=newnode(); now=nxt[now][buf[i]-'a']; } edd[now]++; } void build()//建立ac自动机 { queue<int>que; for(int i=0;i<26;i++) { if(nxt[root][i]==-1)nxt[root][i]=root; else //若有连边则将节点加入队列 ，并将FAIL指针指向root { FAIL[nxt[root][i]]=root; que.push(nxt[root][i]); } } while(!que.empty()) { int now=que.front(); que.pop(); for(int i=0;i<26;i++) { if(nxt[now][i]==-1) //若无连边，则将该边指向当前节点FAIL指针指向的相应字符连接的节点 nxt[now][i]=nxt[FAIL[now]][i]; else //若有连边，则将儿子节点的FAIL指针指向当前节点FAIL指针指向相应字符接的节点 { FAIL[nxt[now][i]]=nxt[FAIL[now]][i]; que.push(nxt[now][i]); //加入队列继续遍历 } } } } int query(char buf[],int l) { int now=root; int res=0; for(int i=0;i<l;i++) { now=nxt[now][buf[i]-'a']; int temp=now; while(temp!=root&&mark[temp]==0)//根据题目要求改变形式 { res+=edd[temp]; edd[temp]=0; mark[temp]=1; temp=FAIL[temp]; } } return res; //在这里返回的是匹配到的模式串的数量 } char buf[maxlen],ans[maxlen]; string A[maxlen]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); int ma=0; for(int i=0;i<n;i++) { scanf("%s",buf); int l=strlen(buf); if(ma<l) { ma=l; strcpy(ans,buf); } insert(buf,l); } build(); int sum=query(ans,ma); if(sum==n) puts(ans); else puts("No"); } }
#include <stdio.h> #include <string.h> char S[1200010]; char *t[1100010],*s; int f[1202020]; void getfail(char p[],int f[]) //字符串p自我匹配 { int len=strlen(p); f[0]=f[1]=0; for(int i=1;i<len;i++) { int j=f[i]; while(j&&p[i]!=p[j]) j=f[j]; if(p[i]==p[j]) f[i+1]=j+1;//多匹配到了一个字符 else f[i+1]=0;//该字符配不上 } } int find(char* T, char*P, int*f)//p去匹配字符串T { int n = strlen(T), m = strlen(P); getfail(P, f); //得出部分匹配表 int j = 0; //短串的下标 for(int i = 0; i < n; i++) //长串下标 { while(j && P[j] != T[i])//突然失配了 { j = f[j]; //j往回退，直到0或者上一个字符相等的位置 } if(P[j] == T[i]) { j++; //匹配了一个字符，j++ } if(j == m) //短串匹配到头了 { return 1;//i - m + 1;//返回成功匹配的起点字符位置 } } return -1; } int main() { int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); int maxlen=0; int p=1;//记录最长串 s=S; for(int i=1;i<=n;i++) { scanf("%s",s); t[i]=s; if(strlen(s)>maxlen){ maxlen=strlen(s); p=i; } s+=strlen(s)+2; } int ans=0; for(int i=1;i<=n;i++) { if(find(t[p],t[i],f)==1) ans++; else break; } if(ans==n) { printf("%s ",t[p]); } else puts("No"); } return 0; }
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define ll long long using namespace std; int f[1000010]; int T,n; char s[2000010]; char *t[120000]; void getfail(char p[]) //字符串p自我匹配 { int len=strlen(p); f[0]=f[1]=0; for(int i=1;i<len;i++) { int j=f[i]; while(j&&p[i]!=p[j]) j=f[j]; if(p[i]==p[j]) f[i+1]=j+1;//多匹配到了一个字符 else f[i+1]=0;//该字符配不上 } } int find(char* T, char*P)//p去匹配字符串T { int n = strlen(T), m = strlen(P); getfail(P); //得出部分匹配表 int j = 0; //短串的下标 for(int i = 0; i < n; i++) //长串下标 { while(j && P[j] != T[i])//突然失配了 { j = f[j]; //j往回退，直到0或者上一个字符相等的位置 } if(P[j] == T[i]) { j++; //匹配了一个字符，j++ } if(j == m) //短串匹配到头了 { return 1;//i - m + 1;//返回成功匹配的起点字符位置 } } return -1; } int main(){ int max_len; scanf("%d",&T); while(T--){ scanf("%d",&n); max_len=0; int tmp; char *qw; char *io=s; for(int i=1 ;i <= n;i++){ scanf("%s",io); tmp=strlen(io); if( tmp > max_len ){ max_len=tmp; qw=io; } t[i]=io; io+=strlen(io)+2; } int flag=1; for(int j=1;j<=n;j++){ if( find(qw,t[j]) != 1 ){ flag=0; break ; } } if(flag){ printf("%s ",qw); } else{ printf("No "); } } return 0; }
#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<vector> using namespace std; typedef long long int LL; int Sunday(string text, string pattern){ 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() { ios::sync_with_stdio(false); 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; }