Advertisement
Josif_tepe

Untitled

Jun 6th, 2023
745
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int ALPHABET_SIZE = 26;
  5. struct node {
  6.     node *children_of_this_node[ALPHABET_SIZE];
  7.     bool end_of_word;
  8.  
  9.     node() {
  10.         end_of_word = false;
  11.         for(int i = 0; i < ALPHABET_SIZE; i++) {
  12.             children_of_this_node[i] = NULL;
  13.         }
  14.     }
  15. };
  16. void insert_word(node * trie, string s) {
  17.     node * tmp = trie;
  18.    
  19.     for(int i = 0; i < (int) s.size(); i++) {
  20.         int current_char = (s[i] - 'a');
  21.         if(tmp -> children_of_this_node[current_char] == NULL) {
  22.             tmp -> children_of_this_node[current_char] = new node();
  23.         }
  24.         tmp = tmp -> children_of_this_node[current_char];
  25.     }
  26.     tmp -> end_of_word = true;
  27. }
  28. bool find_word(node * trie, string s) {
  29.     node * tmp = trie;
  30.    
  31.     for(int i = 0; i < (int) s.size(); i++) {
  32.         int current_char = (s[i] - 'a');
  33.         if(tmp -> children_of_this_node[current_char] == NULL) {
  34.             return false;
  35.         }
  36.         tmp = tmp -> children_of_this_node[current_char];
  37.     }
  38.     return tmp -> end_of_word;
  39. }
  40. int main() {
  41.     int n;
  42.     cin >> n;
  43.    
  44.     node * trie = new node();
  45.     vector<string> dictionary(n);
  46.     for(int i = 0; i < n; i++) {
  47.         cin >> dictionary[i];
  48.         insert_word(trie, dictionary[i]);
  49.     }
  50.    
  51.     int q;
  52.     cin >> q;
  53.     for(int i = 0; i < q; i++) {
  54.         string s;
  55.         cin >> s;
  56.         if(find_word(trie, s)) {
  57.             cout << "YES"<< endl;
  58.         }
  59.         else {
  60.             cout << "NO" << endl;
  61.         }
  62.     }
  63.    
  64.  
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement