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 .
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
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
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][],FAIL[maxlen],edd[maxlen],root,L;//nxt记录节点，在这里edd指针代表以当前节点为字符串尾的字符串个数
int mark[maxlen];
int newnode()
{
for(int i=;i<;i++)
nxt[L][i]=-;//节点连接的边初始化为-1
edd[L]=;
mark[L]=;
return L++;
}
void init()
{
L=;
root=newnode();
} void insert(char buf[],int l)//trie树的建立
{
int now=root;
for(int i=;i<l;i++)
{
if(nxt[now][buf[i]-'a']==-)nxt[now][buf[i]-'a']=newnode();
now=nxt[now][buf[i]-'a'];
}
edd[now]++;
}
void build()//建立ac自动机
{
queue<int>que;
for(int i=;i<;i++)
{
if(nxt[root][i]==-)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=;i<;i++)
{
if(nxt[now][i]==-) //若无连边，则将该边指向当前节点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=;
for(int i=;i<l;i++)
{
now=nxt[now][buf[i]-'a'];
int temp=now;
while(temp!=root&&mark[temp]==)//根据题目要求改变形式
{
res+=edd[temp];
edd[temp]=;
mark[temp]=;
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=;
for(int i=;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");
}
}
AC自动机
#include <stdio.h>
#include <string.h>
char S[];
char *t[],*s;
int f[];
void getfail(char p[],int f[]) //字符串p自我匹配
{
int len=strlen(p);
f[]=f[]=;
for(int i=;i<len;i++)
{
int j=f[i];
while(j&&p[i]!=p[j])
j=f[j];
if(p[i]==p[j])
f[i+]=j+;//多匹配到了一个字符
else
f[i+]=;//该字符配不上
}
}
int find(char* T, char*P, int*f)//p去匹配字符串T
{
int n = strlen(T), m = strlen(P);
getfail(P, f); //得出部分匹配表
int j = ; //短串的下标
for(int i = ; 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 ;//i - m + 1;//返回成功匹配的起点字符位置
}
}
return -;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int maxlen=;
int p=;//记录最长串
s=S;
for(int i=;i<=n;i++)
{
scanf("%s",s);
t[i]=s;
if(strlen(s)>maxlen){
maxlen=strlen(s);
p=i;
}
s+=strlen(s)+;
}
int ans=;
for(int i=;i<=n;i++)
{
if(find(t[p],t[i],f)==)
ans++;
else break;
}
if(ans==n)
{
printf("%s\n",t[p]);
}
else puts("No");
}
return ;
}
KMP
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std; int f[];
int T,n;
char s[];
char *t[]; void getfail(char p[]) //字符串p自我匹配
{
int len=strlen(p);
f[]=f[]=;
for(int i=;i<len;i++)
{
int j=f[i];
while(j&&p[i]!=p[j])
j=f[j];
if(p[i]==p[j])
f[i+]=j+;//多匹配到了一个字符
else
f[i+]=;//该字符配不上
}
}
int find(char* T, char*P)//p去匹配字符串T
{
int n = strlen(T), m = strlen(P);
getfail(P); //得出部分匹配表
int j = ; //短串的下标
for(int i = ; 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 ;//i - m + 1;//返回成功匹配的起点字符位置
}
}
return -;
} int main(){ int max_len;
scanf("%d",&T); while(T--){
scanf("%d",&n);
max_len=;
int tmp;
char *qw;
char *io=s;
for(int i= ;i <= n;i++){
scanf("%s",io);
tmp=strlen(io);
if( tmp > max_len ){
max_len=tmp;
qw=io;
}
t[i]=io;
io+=strlen(io)+;
} int flag=; for(int j=;j<=n;j++){ if( find(qw,t[j]) != ){
flag=;
break ;
}
} if(flag){
printf("%s\n",qw);
}
else{
printf("No\n");
} } return ;
}
another KMP
#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 = , j = , k;
int m = pattern.size(); if(pattern.size() <= || text.size() <= )
return -; for(; i<text.size();) {
if(text[i] != pattern[j]) {
for(k=pattern.size() - ; k>=; k--) {
if(pattern[k] == text[m])
break;
}
i = m-k;
j = ;
m = i+pattern.size();
}
else {
if(j == pattern.size()-)
return i-j;
i++;
j++;
} }
return -;
} 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=;i<n;i++)
{
cin>>t;
if(text.length()<t.length())
text=t;
v.push_back(t);
}
int f=;
for(int i=;i<n;i++)
{
if(Sunday(text,v[i])== -)
{
f=;
break;
}
}
if(f)
cout<<text<<endl;
else
cout<<"No"<<endl;
}
return ;
}
Sunday algorithm