题目大意:有 n 个字符串,m 次询问,每次给定一个字符串,判断该字符串是否在 n 个字符串里出现过。
1≤n≤104,1≤m≤105,1≤s≤50,其中 s 是每个字符串的长度。
#include <cstdio>
#include <cstring>
using namespace std;
struct Trie{
int child[30];
int cnt;
};
Trie T[114514];
int dot;
char c[51];
int n,m;
void insert(char s[]){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int a=s[i]-'a';
if(T[u].child[a]==0) T[u].child[a]=++dot;
u=T[u].child[a];
}
T[u].cnt++;
}
bool find(char s[]){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int a=s[i]-'a';
if(T[u].child[a]==0) return false;
u=T[u].child[a];
}
if(T[u].cnt==0) return false;
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",c);
insert(c);
}
for(int i=1;i<=m;i++){
scanf("%s",c);
if(find(c)) printf("Yes\n");
else printf("No\n");
}
return 0;
}