比赛 |
20160419s |
评测结果 |
ATTAAAATTT |
题目名称 |
情书 |
最终得分 |
50 |
用户昵称 |
mikumikumi |
运行时间 |
5.008 s |
代码语言 |
C++ |
内存使用 |
1.97 MiB |
提交时间 |
2016-04-19 11:24:49 |
显示代码纯文本
#include<cstdio>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEM=1350010,SIZEN=110;
char str[SIZEM];
bool vis[SIZEN];
queue<int> Q;
int pos;
int N;
class miku
{
public:
int cnt;
int fail[SIZEN*SIZEN];
int flag[SIZEN*SIZEN];
map<char,int> next[SIZEN*SIZEN];
miku()
{
cnt=1;
memset(flag,0,sizeof(flag));
for(int i=0;i<=200;i++) next[0][i]=1;
}
void built(char a[],int n,int id)
{
int now=1;
for(int i=0;i<n;i++)
{
char c=a[i];
if(!next[now][c]) next[now][c]=++cnt;
now=next[now][c];
}
flag[now]=id;
}
void makefail()
{
fail[1]=0;
Q.push(1);
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<=200;i++)
{
if(next[x][i])
{
int v=next[x][i];
int k=fail[x];
while(!next[k][i]) k=fail[k];
fail[v]=next[k][i];
Q.push(v);
}
}
}
}
void dfs(int x)
{
if(!x) return;
if(vis[x]) return;
vis[x]=1;
if(flag[x]) pos++;
dfs(fail[x]);
}
void check(char a[])
{
int len=strlen(a)-1,now=1;
pos=0;memset(vis,0,sizeof(vis));
for(int i=0;i<len;i++)
{
int c=a[i];
while(!next[now][c]) now=fail[now];
now=next[now][c];
dfs(now);
}
if(pos==N) printf("Yes\n");
else printf("No\n");
}
}AC;
void read()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%s",str);
//cout<<str<<endl;
int len=strlen(str);
AC.built(str,len,i);
}
AC.makefail();
}
void work()
{
while(true)
{
if(scanf("%s",str)==EOF) break;
AC.check(str);
}
}
int main()
{
freopen("lettera.in","r",stdin);
freopen("lettera.out","w",stdout);
read();
work();
return 0;
}