Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int ALPHABET_SIZE = 26;
- struct node {
- node *children_of_this_node[ALPHABET_SIZE];
- bool end_of_word;
- node() {
- end_of_word = false;
- for(int i = 0; i < ALPHABET_SIZE; i++) {
- children_of_this_node[i] = NULL;
- }
- }
- };
- void insert_word(node * trie, string s) {
- node * tmp = trie;
- for(int i = 0; i < (int) s.size(); i++) {
- int current_char = (s[i] - 'a');
- if(tmp -> children_of_this_node[current_char] == NULL) {
- tmp -> children_of_this_node[current_char] = new node();
- }
- tmp = tmp -> children_of_this_node[current_char];
- }
- tmp -> end_of_word = true;
- }
- bool search_word(node * trie, string s) {
- node * tmp = trie;
- for(int i = 0; i < (int) s.size(); i++) {
- int current_char = (s[i] - 'a');
- if(tmp -> children_of_this_node[current_char] == NULL) {
- return false;
- }
- tmp = tmp -> children_of_this_node[current_char];
- }
- return tmp -> end_of_word;
- }
- int main() {
- int n;
- cin >> n;
- node * trie = new node();
- vector<string> dictionary(n);
- for(int i = 0; i < n; i++) {
- cin >> dictionary[i];
- insert_word(trie, dictionary[i]);
- }
- int q;
- cin >> q;
- for(int i = 0; i < q; i++) {
- string s;
- cin >> s;
- if(search_word(trie, s)) {
- cout << "YES"<< endl;
- }
- else {
- cout << "NO" << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement