CODE[VS]4189 字典 (字典树模板题)

描述

传送门:我是传送门

最经,skyzhong得到了一本好厉害的字典,这个字典里整整有n个单词(1<=n<=200000)

现在skyzhong需要在字典里查询以某一段字母开头的单词

如:skyzhong想查询a

那么只要是a开头的单词就可以了

skyzhong只想知道里面有没有这一个单词(因为没有他就不查了)

若有,请输出YES。若没有,请输出NO

输入

第一行一个数n

第二行到第n+1行,一行一个字符串

再下一行一个数m,表示skyzhong想要查询的次数

接着m行,一行一个字符串,表示skyzhong想要查的东西

输出

共m行,若有这字串输出YES,否则输出NO

样例

输入

3

asd

asfdghj

asfd

3

asd

asdghj

asf

输出

YES

NO

YES

Note

字符串只有小写字母,且长度≤8

思路

字典树的模板题,恰好可以拿来练习字典树的使用

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/*
* =========================================================================
*
* Filename: p4189.cpp
*
* Link: http://codevs.cn/problem/4189/
*
* Version: 1.0
* Created: 2018/08/29 10时31分33秒
* Revision: none
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* =========================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=a;i>=n;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1000100;

struct node
{
int next[27];
}trie[N];
char a[10];
int tot;

void add()
{
int len = strlen(a);
int now = 0;
for(int i = 0;i < len;i++)
{
int tmp = a[i]-'a'+1;
int next = trie[now].next[tmp];
if(next)
{
now = next;
}
else
{
trie[now].next[tmp] = ++tot;
now = tot;
}
}
}

int query()
{
int len = strlen(a);
int now = 0,p = 0;
while(p < len)
{
int tmp = trie[now].next[a[p]-'a'+1];
if(!tmp)
return 0;
else
{
now = tmp;
p++;
}
}
return 1;
}

int main()
{
ios
int n,m;
cin >> n;
rep(i,1,n)
{
cin >> a;
add();
}
cin >> m;
rep(i,1,m)
{
cin >> a;
if(query())
printf("YES\n");
else
printf("NO\n");

}

return 0;
}