C. Watto and Mechanism
time limit per test
memory limit per test
input
output
Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s
Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m
Input
The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of the initial strings and the number of queries, respectively.
Next follow n
Next follow m
The total length of lines in the input doesn't exceed 6·105. Each line consists only of letters 'a', 'b', 'c'.
Output
For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).
Examples
input
2 3
aaaaa
acacaca
aabaa
ccacacc
caaac
output
YES
NO
NO
把字符串挂到Trie树上，对于需要查询的一个字符串str,在Trie上进行深搜找到一个字符串，满足条件
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
int end;
Node *p[3];
};
char str[600005];
Node *NewNode(){
Node *m = new Node();
memset(m, 0, sizeof(Node));
return m;
}
void Insert(Node *root){
Node *h = root;
for(int i = 0; str[i]; i++){
int d = str[i] - 'a';
if(h -> p[d] == 0)
h -> p[d] = NewNode();
h = h -> p[d];
}
h -> end = 1;
}
bool Query(Node *h, int k, int j){
if(str[j] == 0){
if(h -> end == 1 && k == 1)
return true;
return false;
}
int d = str[j] - 'a';
for(int i = 0; i < 3; i++){
if(h -> p[i]){
if(i == d && Query(h -> p[i], k, j+1))
return true;
if(i != d && k == 0 && Query(h -> p[i], k+1, j+1))
return true;
}
}
return false;
}
void Delete(Node *h){
for(int i = 0; i < 3; i++){
if(h -> p[i])
Delete(h -> p[i]);
}
free(h);
}
int main(){
//freopen("in.txt", "r", stdin);
Node *root = NewNode();
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
scanf("%s", str);
Insert(root);
}
for(int i = 0; i < m; i++){
scanf("%s", str);
if(Query(root, 0, 0))
puts("YES");
else
puts("NO");
}
Delete(root);
return 0;
}