Rolling hash

Overview

A rolling hash turns each substring of a fixed length into a number that can be updated in O(1) as the window slides one character: remove the leftmost character's contribution, multiply by the base, and add the new character. Comparing numbers is much faster than comparing strings.

Rabin-Karp uses this to search for a pattern in O(n + m) on average: compare the window's hash with the pattern's hash, and verify characters only when the hashes match. With binary search on length, rolling hashes also find the longest repeated substring. Collisions are possible, so use a large modulus, double hashing, or verification.

When to use it

• Compare many substrings of the same length quickly.
• Find duplicate or repeated substrings (DNA sequences, longest duplicate).
• Pattern search when multiple patterns share a length.
• Combine with binary search on the answer length.

Problem patterns it solves

Where it is used in real software

Key terms

Polynomial hash

hash(s) = s[0] x B^(k-1) + s[1] x B^(k-2) + ... + s[k-1], mod M.

Base B

A number larger than the alphabet size, often 31, 131, or 256.

Modulus M

A large prime such as 1e9 + 7 keeps values bounded.

Collision

Different strings with the same hash; verify or use two hashes.

Prefix hash

h[i] = hash of s[0..i); any substring hash is derived in O(1).

How it works, step by step

1. 1
   Hash the pattern and the first window

   h = (h x B + code) mod M for each character.

2. 2
   Precompute B^(k-1) mod M

   The weight of the leftmost character in a window of length k.

3. 3
   Slide

   h = (h - left x B^(k-1)) x B + right, all mod M, keeping h non-negative.

4. 4
   Compare

   If the hashes match, verify the characters to rule out a collision.

5. 5
   For substring queries

   hash(l, r) = h[r] - h[l] x B^(r - l), mod M.

Rolling a length-3 window over "abcd"

a = 1, b = 2, c = 3, d = 4, base B = 10 (no modulus, for readability)

The second hash came from the first in O(1) instead of rehashing three characters. With base 10 the hash is literally the digits; real implementations use a larger base and a modulus.

Implementation

1// Rabin-Karp with verification; BigInt-free by keeping values below 2^532function rabinKarp(text, pattern) {3  const n = text.length, m = pattern.length;4  if (m === 0) return 0;5  if (m > n) return -1;6  const B = 131, M = 1_000_000_007;7  let high = 1; // B^(m-1) mod M8  for (let i = 1; i < m; i++) high = (high * B) % M;9 10  let hp = 0, ht = 0;11  for (let i = 0; i < m; i++) {12    hp = (hp * B + pattern.charCodeAt(i)) % M;13    ht = (ht * B + text.charCodeAt(i)) % M;14  }15  for (let i = 0; ; i++) {16    if (hp === ht && text.startsWith(pattern, i)) return i; // verify on hash match17    if (i + m >= n) return -1;18    ht = (ht - (text.charCodeAt(i) * high) % M + M) % M; // remove left char19    ht = (ht * B + text.charCodeAt(i + m)) % M;          // add right char20  }21}22 23// 187. Repeated DNA Sequences: 2 bits per base, 20-bit window, exact (no collisions)24function findRepeatedDnaSequences(s) {25  const code = { A: 0, C: 1, G: 2, T: 3 };26  const seen = new Set(), added = new Set(), result = [];27  let hash = 0;28  for (let i = 0; i < s.length; i++) {29    hash = ((hash << 2) | code[s[i]]) & 0xfffff; // keep the last 10 bases30    if (i < 9) continue;31    if (seen.has(hash) && !added.has(hash)) {32      added.add(hash);33      result.push(s.slice(i - 9, i + 1));34    }35    seen.add(hash);36  }37  return result;38}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Negative values after subtraction.

  Fix: Add M before taking the modulus: (h - x + M) % M.

• Overflow in JavaScript multiplication.

  Fix: 131 x (1e9 + 7) is safe, but (1e9) x (1e9) is not; keep one operand small or use BigInt.

• Trusting a hash match without verification.

  Fix: Compare characters on equal hashes, or use double hashing.

Interview questions

Practice problems