kulmak41

Untitled

Nov 28th, 2021
494
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define ssize(a) (int)(a).size()
  4. #define all(a) (a).begin(), (a).end()
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9.  
  10. vector<int> suf_arr(string s) {
  11.     s.push_back('#');
  12.     int n = ssize(s);
  13.  
  14.     vector<int> p(n);
  15.     vector<int> np(n);
  16.     vector<int> c(n);
  17.     vector<int> nc(n);
  18.     vector<int> cnt(n);
  19.     iota(all(p), 0);
  20.     sort(all(p), [&](int i, int j) {
  21.         return s[i] < s[j];
  22.     });
  23.     c[p[0]] = 0;
  24.     for (int i = 1; i < n; ++i) {
  25.         c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
  26.     }
  27.     for (int k = 1; c[p[n - 1]] < n - 1; k *= 2) {
  28.         for (int i = 0; i < n; ++i) {
  29.             np[i] = p[i] - k;
  30.             if (np[i] < 0)
  31.                 np[i] += n;
  32.         }
  33.         fill(all(cnt), 0);
  34.         for (int x : c) {
  35.             ++cnt[x];
  36.         }
  37.         for (int i = 1; i < n; ++i) {
  38.             cnt[i] += cnt[i - 1];
  39.         }
  40.         for (int i = n - 1; i >= 0; --i) {
  41.             p[--cnt[c[np[i]]]] = np[i];
  42.         }
  43.  
  44.         nc[p[0]] = 0;
  45.         for (int i = 1; i < n; ++i) {
  46.             nc[p[i]] = nc[p[i - 1]];
  47.             if (c[p[i]] != c[p[i - 1]]) {
  48.                 ++nc[p[i]];
  49.             } else {
  50.                 int x = p[i - 1] + k;
  51.                 if (x > n)
  52.                     x -= n;
  53.                 int y = p[i] + k;
  54.                 if (y > n)
  55.                     y -= n;
  56.                 if (c[x] != c[y])
  57.                     ++nc[p[i]];
  58.             }
  59.         }
  60.         c.swap(nc);
  61.     }
  62.     p.erase(p.begin());
  63.     return p;
  64. }
  65.  
  66. struct Sparse {
  67.     vector<vector<int>> st;
  68.  
  69.     Sparse(vector<int>& a) {
  70.         int n = ssize(a);
  71.         int logn = __lg(n);
  72.         st.resize(logn + 1, vector<int>(n));
  73.         st[0] = a;
  74.         for (int k = 1; k <= logn; ++k) {
  75.             for (int i = 0; i + (1 << k) <= n; ++i) {
  76.                 st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
  77.             }
  78.         }
  79.     }
  80.  
  81.     int get(int l, int r) {
  82.         int k = __lg(r - l);
  83.         return min(st[k][l], st[k][r - (1 << k)]);
  84.     }
  85. };
  86.  
  87.  
  88. int main() {
  89. #ifdef LOCAL
  90.     freopen("input.txt", "r", stdin);
  91. #endif
  92.     ios_base::sync_with_stdio(false);
  93.     cin.tie(nullptr);
  94.  
  95.     string text;
  96.     vector<int> prefix_len;
  97.     vector<string> ask_s;
  98.     {
  99.         char t;
  100.         string s;
  101.         while (cin >> t >> s) {
  102.             for (auto& c : s) {
  103.                 c = tolower(c);
  104.             }
  105.             if (t == 'A') {
  106.                 text += s;
  107.             } else {
  108.                 prefix_len.push_back(ssize(text));
  109.                 ask_s.push_back(s);
  110.             }
  111.         }
  112.     }
  113.  
  114.     vector<int> sa = suf_arr(text);
  115.     Sparse st(sa);
  116.  
  117. //    for (int i = 0; i < ssize(text); ++i) {
  118. //        cout << i << " " << text.substr(sa[i]) << "\n";
  119. //    }
  120.  
  121.     for (int i = 0; i < ssize(ask_s); ++i) {
  122.         int l = partition_point(all(sa), [&](int j) {
  123.            int k = min(ssize(text), j + ssize(ask_s[i]));
  124.            return lexicographical_compare(text.begin() + j, text.begin() + k, all(ask_s[i]));
  125.         }) - sa.begin();
  126.         int r = partition_point(sa.begin() + l, sa.end(), [&](int j) {
  127.             int k = min(ssize(text), j + ssize(ask_s[i]));
  128.             return !lexicographical_compare(all(ask_s[i]), text.begin() + j, text.begin() + k);
  129.         }) - sa.begin();
  130. //        cout << l << " " << r << " ";
  131.         if (l == r) {
  132.             cout << "NO";
  133.         } else {
  134.             int mn = st.get(l, r);
  135.             if (mn + ssize(ask_s[i]) - 1 < prefix_len[i]) {
  136.                 cout << "YES";
  137.             } else {
  138.                 cout << "NO";
  139.             }
  140.         }
  141.         cout << "\n";
  142.     }
  143.  
  144.  
  145.  
  146.     return 0;
  147. }
RAW Paste Data