比赛 |
20160419s |
评测结果 |
AAAAAAAAAA |
题目名称 |
情书 |
最终得分 |
100 |
用户昵称 |
瑆の時間~無盡輪迴·林蔭 |
运行时间 |
1.011 s |
代码语言 |
C++ |
内存使用 |
231.43 MiB |
提交时间 |
2020-05-09 10:52:48 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<cstring>
#define R register
using namespace std;
int fair[2000001],PD[2000001];
bool PDS[2000001];
int tire[2000001][26];
int tot=0,n;
string X;
inline void ADD(string x)
{
R int p=0;
for(R int i=0;i<x.size();i++)
{
if(tire[p][x[i]-'a'])
{
p=tire[p][x[i]-'a'];
}
else
{
tire[p][x[i]-'a']=++tot;
p=tot;
}
}
PD[p]++;
}
inline void Makefair()
{
queue<int> q;
for(R int i=0;i<26;i++)
{
if(tire[0][i])
q.push(tire[0][i]);
}
while(q.size())
{
int p=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(tire[p][i])
{
//fair[tire[p][i]]=tire[fair[p]][i];
q.push(tire[p][i]);
int FA=fair[p];
while(FA&&!tire[FA][i])
FA=fair[FA];
fair[tire[p][i]]=tire[FA][i];
}
else
tire[p][i]=tire[fair[p]][i];
}
}
}
inline int AC(char *x)
{
R int p=0,ans=0,SE=strlen(x)-1;
for(R int i=0;i<SE;i++)
{
p=tire[p][x[i]-'a'];
for(int j=p;j&&PDS[j]!=-1;j=fair[j])
{
ans+=PD[j];
PDS[j]=-1;
}
}
return ans;
}
char WED[2350010];
int main()
{
freopen("lettera.in", "r", stdin);
freopen("lettera.out", "w", stdout);
scanf("%d",&n);
for(R int i=1;i<=n;i++)
{
cin>>X;
ADD(X);
}
Makefair();
while(scanf("%s",WED)!=EOF)
{
memset(PDS,0,sizeof(0));
if(AC(WED)==n)
{
puts("Yes");
}
else
puts("No");
}
return 0;
}