Advertisement
titovtima

Untitled

Oct 20th, 2020
1,945
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cmath>
  5. #include <map>
  6.  
  7. using namespace std;
  8. using ll = long long;
  9. using ull = unsigned long long;
  10. map<string, bool> ans;
  11. string s;
  12.  
  13. struct Node {
  14.     Node* next[26];
  15.     bool term; //терминальная ли
  16.     Node() {
  17.         for(int i = 0; i < 26; i++) {
  18.             next[i] = nullptr;
  19.         }
  20.         term = false;
  21.     }
  22.     Node(string& w, char c) {
  23.         for(int i = 0; i < 26; i++) {
  24.             next[i] = nullptr;
  25.         }
  26.         term = true;
  27.         word = w + c;
  28.     }
  29.     string word = "";
  30. };
  31.  
  32. struct Trie {
  33.     Node* root;
  34.     Trie() {
  35.         root = new Node();
  36.     }
  37.     void insert(string &s) {
  38.         Node* cur = root;
  39.         for(int i = 0; i < s.length(); i++) {
  40.             char c = s[i];
  41.             if (cur->next[c - 'a'] == nullptr) {
  42.                 cur->next[c - 'a'] = new Node();
  43.             }
  44.             cur->next[c - 'a']->word = cur->word + c;
  45.             cur = cur->next[c - 'a'];
  46.         }
  47.         cur->term = true;
  48.     }
  49.  
  50.     bool find(int suff) {
  51.         Node* cur = root;
  52.         for(int i = 0; suff + i < s.length(); i++) {
  53.             cur = cur->next[s[suff + i] - 'a'];
  54.             if (cur == nullptr) return false;
  55.             if (cur->term) {
  56.                 ans[cur->word] = true;
  57.             }
  58.         }
  59.         return cur->term;
  60.     }
  61. };
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(nullptr);
  66.  
  67.     cin >> s;
  68.     int M; cin >> M;
  69.     vector<string> vec(M);
  70.     Trie trie;
  71.     for(int i = 0; i < M; i++) {
  72.         cin >> vec[i];
  73.         trie.insert(vec[i]);
  74.     }
  75.  
  76.     for(int i = 0; i < s.length(); i++) {
  77.         trie.find(i);
  78.     }
  79.  
  80.     for(int i = 0; i < M; i++) {
  81.         if (ans[vec[i]]) cout << "Yes\n";
  82.         else cout << "No\n";
  83.     }
  84.  
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement