Rolling Hash · Podium

Fix a base b (often 31 or 131) and a modulus M (2^64 in unsigned overflow, or a large prime). The hash of s[0..i) is

H[i] = s[0]*b^{i-1} + s[1]*b^{i-2} + … + s[i-1]

Then hash(l, r) = H[r] - H[l] * b^{r-l} (all mod M). That is prefix sums with a geometric twist.

Use: compare two substrings in O(1) after O(n) setup; count distinct substrings of length k (this track's arena problem); binary-search the LCP of two suffixes.

USACO Gold hashing. CSES String Matching can be hash or KMP — hash is shorter and loses to anti-hash tests if you are sloppy.

Single-mod hash. Production code uses two mods or 2^64 + a prime.js

function buildHash(s, base = 911382323, mod = 1_000_000_007) {
  const n = s.length;
  const H = Array(n + 1).fill(0);
  const P = Array(n + 1).fill(1);
  for (let i = 0; i < n; i++) {
    const v = s.charCodeAt(i) + 1;
    H[i + 1] = Number((BigInt(H[i]) * BigInt(base) + BigInt(v)) % BigInt(mod));
    P[i + 1] = Number((BigInt(P[i]) * BigInt(base)) % BigInt(mod));
  }
  function hash(l, r) {
    const raw = BigInt(H[r]) - (BigInt(H[l]) * BigInt(P[r - l])) % BigInt(mod);
    return Number((raw + BigInt(mod)) % BigInt(mod));
  }
  return { hash };
}

TRACE

s = 'aba', base 10, letters a=1, b=2 (tiny numbers so you can see it).

H[1]

hash('a') = 1.

H = [0, 1, ?, ?]

1 / 4

CHECK

A single 1e9+7 hash got WA on a string problem and AC after you added a second modulus. What happened?

CHECK

Count distinct substrings of length k, n = 1e5, k variable. Complexity?

Checks 0/2

Next lesson