Advertisement
veschii_nevstrui

Untitled

May 19th, 2022
657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ui64 = unsigned long long;
  6. using ui32 = unsigned int;
  7.  
  8. const ui64 BASE = 123;
  9. const ui64 MOD = 1791791791;
  10. const ui32 MAXLEN = 30;
  11.  
  12. vector <ui64> calculate_pws() {
  13.     vector <ui64> ans(MAXLEN + 1);
  14.     ans[0] = 1;
  15.     for (ui32 i = 1; i <= MAXLEN; ++i) {
  16.         ans[i] = ans[i - 1] * BASE % MOD;
  17.     }
  18.     return ans;
  19. }
  20.  
  21. const vector<ui64> PWS = calculate_pws();
  22.  
  23. inline void addSymbolToHash(ui64 &hash, char symb) {
  24.     hash = (hash * BASE + symb) % MOD;
  25. }
  26. inline void removeSymbolFromHash(ui64 &hash, ui32 length, char symb) {
  27.     hash = ((hash - symb * PWS[length - 1]) % MOD + MOD) % MOD;
  28. }
  29.  
  30. inline ui64 calculate_hash(const string& s) {
  31.     ui64 hash = 0;
  32.     for (const auto& ch: s) {
  33.         addSymbolToHash(hash, ch);
  34.     }
  35.     return hash;
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     cout.setf(ios::fixed);
  43.     cout.precision(10);
  44.  
  45.     string t;
  46.     cin >> t;
  47.  
  48.     ui32 n;
  49.     cin >> n;
  50.  
  51.     vector <unordered_map<ui64, ui32> > hashes(MAXLEN + 1);
  52.     unordered_set<ui32> lengths;
  53.  
  54.     for (ui32 i = 0; i < n; ++i) {
  55.         string s;
  56.         cin >> s;
  57.         hashes[s.size()][calculate_hash(s)] = i;
  58.         lengths.insert(s.size());
  59.     }
  60.  
  61.     ui64 current_hash = 0;
  62.     unordered_map<ui32, ui64> length_to_hash;
  63.  
  64.     vector <int> answer(n, 0);
  65.  
  66.     auto check_answer = [&answer, &hashes](ui32 length, ui64 hash) {
  67.         if (length <= MAXLEN) {
  68.             const auto& it = hashes[length].find(hash);
  69.             if (it != hashes[length].end()) {
  70.                 answer[it->second] = 1;
  71.             }
  72.         }
  73.     };
  74.  
  75.     for (ui32 i = 0; i < t.size(); ++i) {
  76.         for (auto &[length, hash]: length_to_hash) {
  77.             removeSymbolFromHash(hash, length, t[i - length]);
  78.             addSymbolToHash(hash, t[i]);
  79.             check_answer(length, hash);
  80.         }
  81.         addSymbolToHash(current_hash, t[i]);
  82.         if (lengths.find(i + 1) != lengths.end()) {
  83.             length_to_hash[i + 1] = current_hash;
  84.         }
  85.         check_answer(i + 1, current_hash);
  86.     }
  87.     for (auto& i: answer) {
  88.         if (i == 0) {
  89.             cout << "No\n";
  90.         } else {
  91.             cout << "Yes\n";
  92.         }
  93.     }
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement