samuel21119

NTHUOJ 12371

Oct 22nd, 2020
696
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. struct HASH {
  6.     ll val, mul, mod, len, D;
  7.     HASH() {val = 0;}
  8.     HASH(ll a, ll b) {
  9.         mul = a, mod = b;
  10.         val = 0;
  11.     }
  12.     HASH(ll a, ll b, string &s, ll l) {
  13.         *this = HASH(a, b);
  14.         len = l;
  15.         D = 1;
  16.         for (int i = 0; i < l; i++) {
  17.             val = (val * mul + s[i]) % mod;
  18.             D = (D * mul) % mod;
  19.         }
  20.     }
  21.     void change(int del, int add) {
  22.         val = (val * mul + add) % mod;
  23.         val = (val + mod - del * D % mod) % mod;
  24.     }
  25.     bool operator== (HASH const &b) const {
  26.         return val == b.val;
  27.     }
  28. };
  29. int q;
  30. ll sum[200010];
  31. ll ans;
  32.  
  33. int main() {
  34.     ios::sync_with_stdio(0);
  35.     cin.tie(0);
  36.     string s1, s2;
  37.     while (cin >> s1 >> s2) {
  38.         HASH h1 = HASH(9487, 99999989, s1, s2.length());
  39.         HASH h2 = HASH(9487, 99999989, s2, s2.length());
  40.         int len1 = s1.length();
  41.         int len2 = s2.length();
  42.         for (int i = 0; i <= len1; i++)
  43.             sum[i] = 0;
  44.         for (int i = len2; i <= len1; i++) {
  45.             sum[i] = h1 == h2;
  46.             if (i != len1)
  47.                 h1.change(s1[i - len2], s1[i]);
  48.         }
  49.         for (int i = 1; i <= len1; i++) {
  50.             sum[i] += sum[i - 1];
  51.         }
  52.         ans = 0;
  53.         cin >> q;
  54.         while (q--) {
  55.             int x, y;
  56.             cin >> x >> y;
  57.             if (y - x + 1 < len2)
  58.                 continue;
  59.             x += len2 - 2;
  60.             ans = max(ans, sum[y] - sum[x]);
  61.         }
  62.         cout << ans << '\n';
  63.     }
  64.     return 0;
  65. }
  66.  
RAW Paste Data