时间限制: 1 s
空间限制: 256000 KB
题目链接http://codevs.cn/problem/4189/
题目描述 Description
最经,skyzhong得到了一本好厉害的字典，这个字典里整整有n个单词(1<=n<=200000)
现在skyzhong需要在字典里查询以某一段字母开头的单词
如:skyzhong想查询a
那么只要是a开头的单词就可以了
skyzhong只想知道里面有没有这一个单词（因为没有他就不查了）
若有，请输出YES。若没有，请输出NO
输入描述 Input Description
第一行一个数n
第二行到第n+1行，一行一个字符串
再下一行一个数m，表示skyzhong想要查询的次数
接着m行，一行一个字符串，表示skyzhong想要查的东西
输出描述 Output Description
共m行，若有这字串输出YES，否则输出NO
样例输入 Sample Input
3
asd
asfdghj
asfd
3
asd
asdghj
asf
样例输出 Sample Output
YES
NO
YES
数据范围及提示 Data Size & Hint
字符串只有小写字母，且长度≤8
emmm。。。这是一道裸题，但这并不重要，下面的代码里并不会有注释，所以说只有大概明白我下面所讲内容的人才会看得明白。
首先我们对于一连串的字符串进行插入：
she
he
say
shr
her
接下来我们模拟字典树的插入过程，先建一个数组trie[i][j] ,其中i为下一个位置的标号，j为字符的数字代码（比如说将a转化为其ASCLL值-'a’就可以得到0-26个的小写字母。。。）首先判断是否首字母是否出现：由于我们是从1往下找到，所以第一个编号i=1时相当于第一层即根节点，我们设置一个标号tot（如下图所示），第一次she的进入后，这棵树就变成了（首先找到根节点，然后我们顺着根节点往下找就好了）
接下来放入he由于i=1时只找到了s，所以he就重新另起一头，将其标记为4
重复操作：
接下来放入say:
之后就是shr:
her:
void insert(char *s,int rt) {
for(int i=0; s[i]; i++) {
int x=s[i]-'a';
if(trie[rt][x]==0) { //现在插入的字母在之前同一节点处未出现过
trie[rt][x]=++tot; //字母插入一个新的位置
}
rt=trie[rt][x]; //为下个字母的插入做准备
}
}
如果上面的图解看明白了，那么这个插入的代码片段也就很清楚了。
之后就是查询，然而题目也说的很明白了，只要求查询以某一段字母开头的单词，所以我们直接从开始找到尾就行了。
int find(char *s,int rt) {
for(int i=0; s[i]; i++) {
int x=s[i]-'a';
if(trie[rt][x]==0)return 0;//以rt为头结点的x字母不存在，返回0
rt=trie[rt][x];//为查询下个字母做准备
}
return 1;
}
当然，这只是字典树，对于查找首字母并不存在第一层树中的单词是否出现过，如果只是单个查询的话KMP就可以解决了，如果是多模匹配的话就只能用AC自动机了。
接下来就是对以上模板的一个简单使用，题目如上所述就不多讲了，代码请看下面：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
void insert(char *s,int rt) {
for(int i=0; s[i]; i++) {
int x=s[i]-'a';
if(trie[rt][x]==0) {
trie[rt][x]=++tot;
}
rt=trie[rt][x];
}
}
int find(char *s,int rt) {
for(int i=0; s[i]; i++) {
int x=s[i]-'a';
if(trie[rt][x]==0)return 0;
rt=trie[rt][x];
}
return 1;
}
char s[22];
int main() {
tot=0;
int rt=0;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf ("%s",s);
insert(s,rt);
}
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf ("%s",s);
if(find(s,rt))printf("YES\n");
else printf("NO\n");
}
return 0;
}