kulmak41

Untitled

Nov 28th, 2021
733
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. const int max_len = 1e5 + 10;
  11. char text[max_len];
  12. int p[max_len];
  13. int np[max_len];
  14. int c[max_len];
  15. int nc[max_len];
  16. int cnt[max_len];
  17. int text_len = 0;
  18.  
  19. const int max_queries = 15740785;
  20. char query_s[max_queries];
  21. int query_begin[max_queries];
  22. int prefix_len[max_queries];
  23. int query_len = 0;
  24. int queries_cnt = 0;
  25.  
  26. void build_sa() {
  27.     int n = text_len;
  28.  
  29.     iota(p, p + n, 0);
  30.     sort(p, p + n, [&](int i, int j) {
  31.         return text[i] < text[j];
  32.     });
  33.     c[p[0]] = 0;
  34.     for (int i = 1; i < n; ++i) {
  35.         c[p[i]] = c[p[i - 1]] + (text[p[i]] != text[p[i - 1]]);
  36.     }
  37.     for (int k = 1; c[p[n - 1]] < n - 1; k *= 2) {
  38.         for (int i = 0; i < n; ++i) {
  39.             np[i] = p[i] - k;
  40.             if (np[i] < 0)
  41.                 np[i] += n;
  42.         }
  43.         memset(cnt, 0, sizeof cnt);
  44.         for (int i = 0; i < n; ++i) {
  45.             ++cnt[c[i]];
  46.         }
  47.         for (int i = 1; i < n; ++i) {
  48.             cnt[i] += cnt[i - 1];
  49.         }
  50.         for (int i = n - 1; i >= 0; --i) {
  51.             p[--cnt[c[np[i]]]] = np[i];
  52.         }
  53.  
  54.         nc[p[0]] = 0;
  55.         for (int i = 1; i < n; ++i) {
  56.             nc[p[i]] = nc[p[i - 1]];
  57.             if (c[p[i]] != c[p[i - 1]]) {
  58.                 ++nc[p[i]];
  59.             } else {
  60.                 int x = p[i - 1] + k;
  61.                 if (x > n)
  62.                     x -= n;
  63.                 int y = p[i] + k;
  64.                 if (y > n)
  65.                     y -= n;
  66.                 if (c[x] != c[y])
  67.                     ++nc[p[i]];
  68.             }
  69.         }
  70.         memcpy(c, nc, sizeof c);
  71.     }
  72. }
  73.  
  74.  
  75. const int max_log = 18;
  76. int st[max_log][max_len];
  77.  
  78. void build_st() {
  79.     int n = text_len;
  80.     int logn = __lg(n);
  81.     for (int i = 0; i < n; ++i) {
  82.         st[0][i] = p[i];
  83.     }
  84.     for (int k = 1; k <= logn; ++k) {
  85.         for (int i = 0; i + (1 << k) <= n; ++i) {
  86.             st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
  87.         }
  88.     }
  89. }
  90.  
  91. int get_min(int l, int r) {
  92.     int k = __lg(r - l);
  93.     return min(st[k][l], st[k][r - (1 << k)]);
  94. }
  95.  
  96. int main() {
  97.     ios_base::sync_with_stdio(false);
  98.     cin.tie(nullptr);
  99.     freopen("nenokku.in", "r", stdin);
  100.  
  101.     {
  102.         char t;
  103.         string s;
  104.         while (cin >> t >> s) {
  105.             for (auto& c : s) {
  106.                 c = tolower(c);
  107.             }
  108.             if (t == 'A') {
  109.                 for (auto& c : s) {
  110.                     text[text_len++] = c;
  111.                 }
  112.             } else {
  113.                 query_begin[queries_cnt] = query_len;
  114.                 prefix_len[queries_cnt] = text_len;
  115.                 ++queries_cnt;
  116.                 for (auto& c : s) {
  117.                     query_s[query_len++] = c;
  118.                 }
  119.             }
  120.         }
  121.     }
  122.  
  123.     text[text_len++] = '#';
  124.  
  125.     build_sa();
  126.     build_st();
  127.  
  128.     for (int i = 0; i < queries_cnt; ++i) {
  129.         int end = (i == queries_cnt - 1 ? query_len : query_begin[i + 1]);
  130.         string s(query_s + query_begin[i], query_s + end);
  131.         int s_len = end - query_begin[i];
  132.  
  133.         int l, r;
  134.  
  135.         int low = 0;
  136.         int high = text_len;
  137.         while (high - low > 1) {
  138.             int mid = (low + high) >> 1;
  139.             int k = 0;
  140.             int suf = p[mid];
  141.             while (k < s_len && text[suf + k] == s[k])
  142.                 ++k;
  143.             if (k == s_len || text[suf + k] > s[k])
  144.                 high = mid;
  145.             else
  146.                 low = mid;
  147.         }
  148.  
  149.         l = high;
  150.  
  151.         low = 0;
  152.         high = text_len;
  153.         while (high - low > 1) {
  154.             int mid = (low + high) >> 1;
  155.             int k = 0;
  156.             int suf = p[mid];
  157.             while (k < s_len && text[suf + k] == s[k])
  158.                 ++k;
  159.             if (k < s_len && text[suf + k] > s[k])
  160.                 high = mid;
  161.             else
  162.                 low = mid;
  163.         }
  164.  
  165.         r = high;
  166.  
  167.         if (l == r) {
  168.             cout << "NO";
  169.         } else {
  170.             int mn = get_min(l, r);
  171.             if (mn + ssize(s) - 1 < prefix_len[i]) {
  172.                 cout << "YES";
  173.             } else {
  174.                 cout << "NO";
  175.             }
  176.         }
  177.         cout << "\n";
  178.     }
  179.  
  180.     return 0;
  181. }
RAW Paste Data