比赛 |
20160419s |
评测结果 |
ATTAAAATTT |
题目名称 |
情书 |
最终得分 |
50 |
用户昵称 |
Fmuckss |
运行时间 |
5.019 s |
代码语言 |
C++ |
内存使用 |
20.55 MiB |
提交时间 |
2016-04-19 11:10:07 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 1e5;
int n;
class ac_m {
private:
bool app[105];
int fail[maxn];
map<char, int> ns[maxn];
int node_cnt;
int last[maxn];
int end[maxn];
public:
void insert(char *a, int num) {
int now = 0;
for(int i = 1; a[i]; i++) {
if(!ns[now][a[i]]) ns[now][a[i]] = ++node_cnt;
now = ns[now][a[i]];
if(!a[i+1]) end[now] = num;
}
}
void build() {
queue<int> q;
for(int i = 'a'; i <= 'z'; i++) if(ns[0][i]) q.push(ns[0][i]);
while(!q.empty()) {
int now = q.front(); q.pop();
for(int i = 'a'; i <= 'z'; i++) {
int son = ns[now][i];
if(!son) continue;
q.push(son);
int f = fail[now];
while(f && !ns[f][i]) f = fail[f];
fail[son] = ns[f][i];
last[son] = end[ fail[son] ] ? fail[son] : last[ fail[son] ];
}
}
}
void check(int now) {
if(now) {
app[end[now]] = true;
check(last[now]);
}
}
bool query(char *a) {
memset(app, 0, sizeof(app));
int now = 0;
for(int i = 1; a[i]; i++) {
while(now && !ns[now][a[i]]) now = fail[now];
now = ns[now][a[i]];
if(end[now]) check(now);
else check(last[now]);
}
for(int i = 1; i <= n; i++) {
if(app[i]) continue;
return false;
}
return true;
}
}ac;
char q[105][105];
char la[maxn*200];
bool get_line(char *a) {
int i = 0;
char tmp = getchar();
while((tmp < 'a' || tmp > 'z') && (tmp < 'A' || tmp > 'Z')) {
if(tmp == EOF) return false;
tmp = getchar();
}
while(tmp != '$') {
a[++i] = tmp;
tmp = getchar();
}
a[++i] = '\0';
return true;
}
void read() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%s", q[i]+1);
ac.insert(q[i], i);
}
}
void solve() {
ac.build();
while(get_line(la)) {
if(ac.query(la)) printf("Yes\n");
else printf("No\n");
}
}
int main() {
freopen("lettera.in", "r", stdin);
freopen("lettera.out", "w", stdout);
read();
solve();
return 0;
}