题目描述 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
Trie树模板题
1.指针版
#include<bits/stdc++.h> #define N 2000010 using namespace std;
//map<string ,int>W; //map淼
int n,m,len,tot,trie[N][],sum[N],v[N];
char s[];
struct node{
int count;
node *next[];
node(){count=,memset(next,,sizeof(next));}
}*rt; void insert(){
node *r=rt;
char *word=s;
while(*word){
int id=*word-'a';
if(r->next[id]==NULL) r->next[id]=new node;//r->next[id]=build();
r=r->next[id];
r->count++;
word++;
}
}
int search(){
node *r=rt;
char *word=s;
while(*word){
int id=*word-'a';
r=r->next[id];
if(r==NULL) return ;
word++;
}return r->count;
} int main()
{
rt=new node;
cin>>n;
for(int i=;i<=n;i++){
cin>>s;
insert();
}cin>>m;
for(int i=;i<=m;i++){
cin>>s;
if(search()!=){
cout<<"YES\n";
}else cout<<"NO\n";
}return ;
}
2.数组模拟
#include<bits/stdc++.h> #define N 2000010 using namespace std;
//map<string ,int>W; //map淼
int n,m,len,tot,trie[N][],rt,sum[N],v[N];
char s[];
void insert(){
len=strlen(s);
rt=;
for(int i=;s[i];i++){
int id=s[i]-'a';
if(!trie[rt][id]) trie[rt][id]=++tot;
sum[trie[rt][id]]++;
rt=trie[rt][id];
}
}
int search(){
len=strlen(s);
rt=;
for(int i=;s[i];i++){
int id=s[i]-'a';
if(!trie[rt][id]) return ;
rt=trie[rt][id];
}return sum[rt];
}
int main()
{
cin>>n;
for(int i=;i<=n;i++){
cin>>s;
insert();
}cin>>m;
for(int i=;i<=m;i++){
cin>>s;
if(search()!=){
cout<<"YES\n";
}else cout<<"NO\n";
}return ;
}
3.Map水题版
#include<bits/stdc++.h> using namespace std;
map<string ,int>W;
int n,m,len;
char s[];
int main()
{
cin>>n;
for(int i=;i<=n;i++){
cin>>s;
len=strlen(s);
for(int i=len;i>=;i--){
s[i]='\0';
W[s]++;
}
}cin>>m;
for(int i=;i<=m;i++){
cin>>s;
if(W[s]!=){
cout<<"YES\n";
}else cout<<"NO\n";
}return ;
}
Trie树初探,参考博客:TRTTG
#1014 : Trie树
建树+查找
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10101010 using namespace std; int n,m,tot,tri[N][],vi[N];
string s; void insert(){
int l=s.length(),root=;
for(int i=;i<l;i++){
int id=s[i]-'a';
if(!tri[root][id]) tri[root][id]=++tot;
root=tri[root][id];
vi[root]++;
}
} int ask_(){
int l=s.length(),root=;
for(int i=;i<l;i++){
int id=s[i]-'a';
if(!tri[root][id]) return ;
root=tri[root][id];
}
return vi[root];
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) {
cin>>s;
insert();
}
scanf("%d",&m);
for(int i=;i<=m;i++){
cin>>s;
printf("%d\n",ask_());
}
return ;
}