# 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;``````