trafik

fuckinghashtable

Apr 17th, 2022
856
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <string>
  5. #include <map>
  6. #define ll long long
  7. #define len(v) (int)v.size()
  8. #define all(v) v.begin(), v.end()
  9. using namespace std;
  10.  
  11. struct para {
  12.     ll x;
  13.     ll y;
  14. };
  15. ll p1 = 29, p2 = 239, m = 2e5 + 3;
  16.  
  17. bool operator==(const para& a, const para& b) {
  18.     return a.x == b.x && a.y == b.y;
  19. }
  20. namespace std {
  21.     template <>
  22.     struct hash<para> {
  23.         std::size_t operator()(const para& k) const
  24.         {
  25.             return (k.x + k.y) % m;
  26.         }
  27.     };
  28. }
  29.  
  30. string t;
  31. unordered_map<para, int> words;
  32.  
  33. para geth(string s) {
  34.     ll h1 = 0;
  35.     for (int i = 0; i < len(s); ++i) {
  36.         h1 = ((h1 * p1) % m + (s[i] - 'a' + 1)) % m;
  37.     }
  38.     ll h2 = 0;
  39.     for (int i = 0; i < len(s); ++i) {
  40.         h2 = ((h2 * p2) % m + (s[i] - 'a' + 1)) % m;
  41.     }
  42.     return {h1, h2};
  43. }
  44.  
  45. void addword(string s, int key) {
  46.     para Hash = geth(s);
  47.     while (words[Hash] != 0) {
  48.         Hash.x = (Hash.x + 1) % m;
  49.         Hash.y = (Hash.y + 1) % m;
  50.     }
  51.     words[Hash] = key;
  52. }
  53.  
  54. vector<string> str;
  55.  
  56. int srch(string s) {
  57.     para Hash = geth(s);
  58.     if (str[words[Hash]] == s) return words[Hash];
  59.     if (words[Hash] == 0) return -1;
  60.     while (words[Hash] != 0 || str[words[Hash]] != s) {
  61.         Hash.x = (Hash.x + 1) % m;
  62.         Hash.y = (Hash.y + 1) % m;
  63.     }
  64.     if (str[words[Hash]] == s) return words[Hash];
  65.     if (words[Hash] == 0) return -1;
  66. }
  67.  
  68.  
  69. int q;
  70. void solve() {
  71.     cin >> t >> q;
  72.     str.resize(q + 1);
  73.     //vector<string> str(q + 1);
  74.     for (int i = 1; i <= q; ++i) {
  75.         string a;
  76.         cin >> a;
  77.         str[i] = a;
  78.         addword(a, i);
  79.     }
  80.     vector<bool> res(q);
  81.     for (int i = 0; i < len(t); ++i) {
  82.         string tmp = "";
  83.         for (int k = 0; (k <= 30 && (i + k) < len(t)); ++k) {
  84.             tmp += t[i + k];
  85.             int n = srch(tmp);
  86.             if (n > -1) res[n - 1] = true;
  87.         }
  88.     }
  89.     for (auto el : res) {
  90.         cout << (el == 1 ? "Yes\n" : "No\n");
  91.     }
  92. }
  93.  
  94. int main() {
  95.     ios::sync_with_stdio(false);
  96.     cin.tie(nullptr);
  97.     cout.tie(nullptr);
  98.  
  99.     solve();
  100.     return 0;
  101. }
  102.  
Advertisement
Add Comment
Please, Sign In to add comment