Rolling Hash (Hashing)

Polynomial rolling hash with double hashing for collision-resistant O(1) substring comparison.

[Strings]|

Jul 9, 2026

|explanatory_notes.md|

#hashing#rolling-hash#double-hash#substring#anti-hack

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct RollingHash {
    static ll p1, p2, m1, m2;
    int n;
    vector<ll> pw1, pw2, h1, h2;

    static void init() {
        static bool done = false;
        if (done) return; done = true;
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        const ll bases[] = {307, 509, 1009, 2003, 3001, 4001};
        const ll mods[] = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093};
        p1 = bases[rng() % 6]; p2 = bases[rng() % 6];
        m1 = mods[rng() % 6]; m2 = mods[rng() % 6];
    }

    RollingHash() {}
    RollingHash(const string &s) { build(s); }

    void build(const string &s) {
        init();
        n = s.size();
        pw1.resize(n + 1); pw2.resize(n + 1);
        h1.resize(n + 1); h2.resize(n + 1);
        pw1[0] = pw2[0] = 1;
        h1[0] = h2[0] = 0;
        for (int i = 1; i <= n; i++) {
            pw1[i] = pw1[i-1] * p1 % m1;
            pw2[i] = pw2[i-1] * p2 % m2;
            h1[i] = (h1[i-1] * p1 + s[i-1]) % m1;
            h2[i] = (h2[i-1] * p2 + s[i-1]) % m2;
        }
    }

    pair<ll, ll> sub(int l, int r) const {
        ll f = (h1[r] - h1[l-1] * pw1[r-l+1] % m1 + m1) % m1;
        ll s = (h2[r] - h2[l-1] * pw2[r-l+1] % m2 + m2) % m2;
        return {f, s};
    }

    pair<ll, ll> merge(int l1, int r1, int l2, int r2) const {
        auto [a1, a2] = sub(l1, r1);
        auto [b1, b2] = sub(l2, r2);
        return {(a1 * pw1[r2-l2+1] + b1) % m1, (a2 * pw2[r2-l2+1] + b2) % m2};
    }

    bool equal(int l1, int r1, int l2, int r2) const {
        return sub(l1, r1) == sub(l2, r2);
    }
};
ll RollingHash::p1, RollingHash::p2, RollingHash::m1, RollingHash::m2;

54 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Rolling Hash

Polynomial hash with double hashing for $O(1)$ substring comparison after $O(n)$ preprocessing.

Hash Definition

H(s) = \sum_{i=0}^{n-1} s[i] \cdot p^{n-1-i} \bmod m

Using prefix hashes $H[i] = H(s[0..i-1])$ , substring $s[l..r]$ (1-indexed):

\text{hash}(l, r) = H[r] - H[l-1] \cdot p^{r-l+1} \bmod m

Double Hashing

Two independent $(p, m)$ pairs. Match only when both components agree. Collision probability $\approx 1/(m_1 \cdot m_2) \approx 10^{-18}$ .

Anti-Hack

Bases and moduli chosen randomly at runtime from pools of safe primes. Prevents adversarial collisions in contests.

Operations

sub(l, r) — hash of substring

[l, r]

O(1)

mergeHash(l1, r1, l2, r2) — concatenate two substring hashes without re-scanning

equal(l1, r1, l2, r2) — check if two substrings match

When to Use

Substring equality checks (pattern matching, longest common substring)

String period detection

Comparing substrings across different strings

Complexity

Build —

O(n)

Query —

O(1)

per substring hash

Space —

O(n)