Rolling Hash
O(1) per substring hashPolynomial hashing with a random base under the Mersenne prime 2^61−1, which survives anti-hash tests that kill fixed-base mod-1e9+7 hashes. Compare any two substrings in O(1). When collisions truly matter, compare with two independent Hash instances.
// use it on
Codeforces 1200E: Compress Words ↗
Merge words by the longest overlap of suffix and prefix. Hash both strings and binary-search / scan overlap lengths with O(1) comparisons.
// the code
struct Hash { // random-base polynomial hash mod 2^61 - 1
static const unsigned long long MOD = (1ULL << 61) - 1;
static unsigned long long B;
vector<unsigned long long> h, p;
static unsigned long long mulmod(unsigned long long a,
unsigned long long b) {
__uint128_t c = (__uint128_t)a * b;
unsigned long long r = (unsigned long long)((c >> 61) + (c & MOD));
return r >= MOD ? r - MOD : r;
}
Hash(const string& s) : h(s.size() + 1, 0), p(s.size() + 1, 1) {
for (size_t i = 0; i < s.size(); i++) {
h[i + 1] = (mulmod(h[i], B) + s[i]) % MOD;
p[i + 1] = mulmod(p[i], B);
}
}
unsigned long long get(int l, int r) { // hash of s[l..r]
unsigned long long res = h[r + 1] + MOD - mulmod(h[l], p[r + 1 - l]);
return res >= MOD ? res - MOD : res;
}
};
unsigned long long Hash::B =
mt19937_64(chrono::steady_clock::now().time_since_epoch().count())() %
(Hash::MOD - 512) + 256;