Advertisement
Josif_tepe

Untitled

Jun 6th, 2023
793
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.15 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 search_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. void delete_word(node * trie, string s) {
  41.     node * tmp = trie;
  42.    
  43.     for(int i = 0; i < (int) s.size(); i++) {
  44.         int current_char = (s[i] - 'a');
  45.         if(tmp -> children_of_this_node[current_char] == NULL) {
  46.             return;
  47.         }
  48.         tmp = tmp -> children_of_this_node[current_char];
  49.     }
  50.     tmp -> end_of_word = false;
  51. }
  52. int main() {
  53.     int n;
  54.     cin >> n;
  55.    
  56.     node * trie = new node();
  57.     vector<string> dictionary(n);
  58.     for(int i = 0; i < n; i++) {
  59.         cin >> dictionary[i];
  60.         insert_word(trie, dictionary[i]);
  61.     }
  62.    
  63.     int q;
  64.     cin >> q;
  65.     for(int i = 0; i < q; i++) {
  66.         char c;
  67.         cin >> c;
  68.         if(c == 'D') {
  69.             string s;
  70.             cin >> s;
  71.             delete_word(trie, s);
  72.         }
  73.         else {
  74.             string s;
  75.             cin >> s;
  76.             if(search_word(trie, s)) {
  77.                 cout << "YES" << endl;
  78.             }
  79.             else {
  80.                 cout << "NO" << endl;
  81.             }
  82.         }
  83.     }
  84.    
  85.  
  86.     return 0;
  87. }
  88.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement