Rolling Hash Template

constexpr int kMaxN = 30'005;

class RollingHash {
 public:
  using ll = long long;
  int hashes[kMaxN];
  int bases[kMaxN];
  int bases_reverse[kMaxN];

  // static int hashes[kMaxN];
  // static int bases[kMaxN];
  // static int bases_reverse[kMaxN];

  const int kBase;
  const int kMod;

  RollingHash(string_view text, int kBase, int kMod)
      : kBase(kBase), kMod(kMod) {
    ll sum = 0;
    ll base = 1;
    int i = 0;
    for (auto const& ch : text) {
      sum += (ch - '0') * base;
      sum %= kMod;
      hashes[i] = sum;
      bases[i] = base;
      bases_reverse[i] = GetReverse(base);
      base = (base * kBase) % kMod;
      i++;
    }
  }

  // s[i, i + len - 1], s[j, j + len - 1]
  bool Equal(int i, int j, int len, string_view const& text) {
    int hash0 = (GetRelativeHash(i, i + len - 1) * bases[j]) % kMod,
        hash1 = (GetRelativeHash(j, j + len - 1) * bases[i]) % kMod;
    if (hash0 != hash1) {
      return false;
    } else {
      return text.substr(i, len) == text.substr(j, len);
    }
  }

  int GetHash(int left, int right) {
    return (GetRelativeHash(left, right) * bases_reverse[left]) % kMod;
  }

 private:
  // https://oi-wiki.org/math/fermat/
  // https://oi-wiki.org/math/inverse/
  ll GetReverse(int val) { return FastPower(val, kMod - 2); }

  ll FastPower(ll val, unsigned int n) {
    if (n == 0) {
      return 1;
    }
    if (n == 1) {
      return val;
    }
    if (n % 2 == 0) {
      return FastPower((val * val) % kMod, n / 2);
    }
    return (FastPower((val * val) % kMod, (n - 1) / 2) * val) % kMod;
  }

  ll GetRelativeHash(int left, int right) {
    return ((ll)hashes[right] - ((left >= 1) ? hashes[left - 1] : 0) + kMod) %
           kMod;
  }
};

// int RollingHash::hashes[kMaxN];
// int RollingHash::bases[kMaxN];
// int RollingHash::bases_reverse[kMaxN];

struct PairHash {
  size_t operator() (pair const& p) const {
    return p.first ^ p.second;
  }
};
unordered_set, PairHash> visited;