Rolling Hash Template

With a Prime Modular

constexpr int kMaxN = 30'005;
class RollingHash {
public:
  using ll = unsigned long long;
  ll hashes[kMaxN];
  ll base_to_i[kMaxN];
  ll base_to_i_inverse[kMaxN];
  
  const int kBase;
  const int kMod;
  
  RollingHash(string_view str, int kBase, int kMod) : kBase(kBase), kMod(kMod) {
    int n = str.size();
    ll curr_base = 1;
    ll curr_sum = 0;
    for (int i = 0; i < n; ++i) {
      curr_sum += (str[i] - 'a') * curr_base; 
      curr_sum %= kMod;
      hashes[i] = curr_sum;
      base_to_i[i] = curr_base;
      curr_base = (curr_base * kBase) % kMod;
    }
    
    base_to_i_inverse[n - 1] = GetInverse(base_to_i[n - 1]);
    for (int i = n - 2; i >= 0; --i) {
      base_to_i_inverse[i] = (base_to_i_inverse[i + 1] * kBase) % kMod;
    }
  }
  
  // s[i, i + len - 1], s[j, j + len - 1]
  bool Equal(int i, int j, int len, string_view str) {
    int hash0 = (GetRelativeHash(i, i + len - 1) * base_to_i[j]) % kMod, hash1 = (GetRelativeHash(j, j + len - 1) * base_to_i[i]) % kMod;
    // if (hash0 != hash1) {
    //     return false;
    // } else {
    //     return str.substr(i, len) == str.substr(j, len);
    // }
    return hash0 == hash1;
  }
  
  int GetHash(int left, int right) {
    return (GetRelativeHash(left, right) * base_to_i_inverse[left]) % kMod;
  }

private:
  // https://oi-wiki.org/math/fermat/
  // https://oi-wiki.org/math/inverse/
  ll GetInverse(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]  + kMod - ((left >= 1) ? hashes[left - 1] : 0)) % kMod;
  }
};

2^64 as a Modular

constexpr int kMaxN = 30'005;
using ll = uint64_t;

// use 2^64 as kMod
class RollingHash {
public:
  const int kBase;
  
  ll hashes[kMaxN];
  ll base_to_i[kMaxN];

  // hashes[i] = s[n - 1] * kBase^n-1-i + s[n - 2] * kBase^n-2-i + s[i] * kBase^0
  RollingHash(string_view str, int kBase) : kBase(kBase) {
    int n = str.size();
    hashes[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
      hashes[i] = hashes[i + 1] * kBase + (str[i] - 'a');
    }
    
    base_to_i[0] = 1;
    for (int i = 1; i < n; ++i) {
      base_to_i[i] = base_to_i[i - 1] * kBase;
    }
  }
  
  // H(4) = s[4]
  // H(3) = s[4] * kBase + s[3]
  // H([3, 3]) = s[3]
  ll GetHash(int left, int right) {
    return hashes[left] - hashes[right + 1] * base_to_i[right - left + 1];
  }
};

Two Hash Functions

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