StringsAlgorithmaka polynomial hash, prefix hashes, string fingerprinting

Rolling Hash (Polynomial Hashing)

Precompute prefix hashes so the hash of any substring — and hence substring equality — can be evaluated in O(1).

▶ VisualizePattern: Binary SearchPractice (2)
Progress

Overview

A polynomial rolling hash maps a string to h(s) = (s[0]·B^(k-1) + s[1]·B^(k-2) + … + s[k-1]) mod M. Storing the hashes of all prefixes, H[i] = h(s[0..i)), lets you evaluate the hash of any substring s[l..r) as (H[r] - H[l]·B^(r-l)) mod M — a single subtraction and multiplication.

This turns substring equality, a naturally O(length) operation, into an O(1) probabilistic one. It underpins Rabin–Karp, "longest duplicate substring" via binary search, palindrome tests by hashing the reversed string, and many suffix-structure replacements in contests. Collisions are possible; picking M around 10^9 (or two moduli) keeps them negligible.

hashingpolynomial hashO(1) substring compareprefix hashesmodular arithmetic

Intuition

A mental model before the formal terms.

Read a string as a number in base B. The prefix s[0..r) is a big number; the prefix s[0..l) is its leading digits. Shifting the leading part left by r - l places (multiplying by B^(r-l)) lines it up with the longer number, and subtracting leaves exactly the digits of s[l..r). Doing everything modulo M keeps the numbers machine-sized at the price of rare collisions.

How it works

  1. Choose a base B larger than the alphabet (e.g. 131 or a random value in [256, M)) and a large prime M (e.g. 10^9 + 7).
  2. Compute H[0] = 0, H[i+1] = (H[i]·B + s[i]) mod M, and P[0] = 1, P[i+1] = P[i]·B mod M.
  3. Hash of s[l..r): (H[r] - H[l]·P[r-l]) mod M, adding M if the difference is negative.
  4. Two substrings are (probably) equal iff their hashes are equal. Verify by direct comparison when a wrong answer is unacceptable.

Why it works

H[r] = H[l]·B^(r-l) + h(s[l..r)) holds exactly over the integers because the polynomial of the longer prefix is the polynomial of the shorter one shifted by r - l positions plus the polynomial of the middle part. Reducing modulo M preserves the identity.

For a fixed pair of distinct strings the hash values collide only if M divides a specific non-zero polynomial evaluated at B. With B chosen at random such a degree-k polynomial has at most k roots, so the collision probability is at most k/M. Comparing n² pairs (the birthday effect) with a single 10^9 modulus is risky; use two moduli or a 61-bit Mersenne modulus.

Recognition

How to tell a problem wants this.

  • Many substring equality tests on one string — "are s[a..b) and s[c..d) equal?" answered repeatedly.
  • Binary search on a length combined with a "does a duplicate of this length exist?" check.
  • Palindrome checks on arbitrary substrings (hash s and reverse(s)).
  • Comparing substrings lexicographically in O(log n) by hashing to find the first mismatch.
“sorted array” → Binary Search“have you seen this before” → Hashing

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Rabin–Karp visualization.

a
a
0
b
1
x
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
y
11
pattern
a
0
b
1
c
2
a
3
b
4
y
5
1/17Use a rolling hash with base 256 modulo 101. h = base^(m-1) mod q = 36 is the weight of the window's leading character.
Current text windowVerifying a hash hitMatchSpurious hit (hash equal, text differs)
PseudocodeLearn Rabin–Karp →
1h = base^(m-1) mod q
2hp = hash(pattern); ht = hash(text[0..m-1])
3for s in 0 .. n-m:
4  if hp == ht:
5    verify text[s..s+m-1] == pattern  # rule out spurious hit
6  if s < n-m:
7    ht = (base*(ht - text[s]*h) + text[s+m]) mod q
Variables
base256
q101
h36
Complexity
best O(n + m)
avg O(n + m)
worst O(n · m)
space O(1)
Speed

Pseudocode

1H[0] = 0, P[0] = 1
2for i in 0 .. n-1:
3  H[i+1] = (H[i] * B + s[i]) mod M
4  P[i+1] = (P[i] * B) mod M
5hash(l, r) = (H[r] - H[l] * P[r-l] mod M + M) mod M

Implementations

1class RollingHash:
2    """A rolling hash turns "is this substring equal to that one" into an O(1)
3    integer comparison. Polynomial hashing: h(s) = sum s[i] * base^(n-1-i)
4    mod m. Prefix hashes recover any substring hash with one subtraction."""
5 
6    MOD = (1 << 61) - 1  # Mersenne prime
7 
81 · prefix[i] hashes s[0..i), and powers[i] is base^i mod m
9    def __init__(self, s: str, base: int = 131) -> None:
10        self.base = base
11        n = len(s)
12        self.prefix = [0] * (n + 1)
13        self.powers = [1] * (n + 1)
142 · One left-to-right pass builds every prefix hash
15        for i, ch in enumerate(s):
16            self.prefix[i + 1] = (self.prefix[i] * base + ord(ch)) % self.MOD
17            self.powers[i + 1] = self.powers[i] * base % self.MOD
18 
193 · hash(s[lo..hi)) = prefix[hi] - prefix[lo] * base^(hi-lo)
20    def substring(self, lo: int, hi: int) -> int:
21        return (self.prefix[hi] - self.prefix[lo] * self.powers[hi - lo]) % self.MOD
22 
23    def equal_ranges(self, lo1: int, lo2: int, length: int) -> bool:
24        return self.substring(lo1, lo1 + length) == self.substring(lo2, lo2 + length)
25 
26 
274 · Rabin-Karp: slide a window and compare hashes, verify on a match
28def rabin_karp(text: str, pattern: str) -> list[int]:
29    n, m = len(text), len(pattern)
30    if m == 0 or m > n:
31        return []
32    th = RollingHash(text)
33    target = RollingHash(pattern).substring(0, m)
34    hits = []
35    for i in range(n - m + 1):
365 · A hash match is not proof — compare the characters before accepting
37        if th.substring(i, i + m) == target and text[i : i + m] == pattern:
38            hits.append(i)
39    return hits
Walkthrough
  1. Python integers are unbounded, so no BigInt ceremony and no __int128 — the arithmetic is written exactly as the mathematics.
  2. substring needs no negative normalisation: Python % returns a non-negative result for a positive modulus, so the subtraction is safe as written.
  3. ord(ch) gives the Unicode *code point*, not a UTF-16 unit, so Python hashes by character in a way JavaScript does not.
  4. for i, ch in enumerate(s) iterates index and character together, avoiding repeated indexing.
  5. text[i : i + m] == pattern verifies the match; the slice allocates, which is the main cost difference from the other three languages.
Complexity (this implementation)
time O(n) to build, O(1) per substring hash; O(n + m) expected for Rabin-Karp · space O(n) for the prefix and power tables

The verification slice allocates O(m) per candidate; text.startswith(pattern, i) avoids that and is the better spelling.

Language notes
  • str.startswith(prefix, start) compares in place with no allocation and is preferable to slicing for verification.
  • in and str.find use a mix of Crochemore-Perrin and Boyer-Moore-Horspool in CPython and are extremely fast — a hand-written Rabin-Karp is for multi-pattern or repeated-query use, not for a single search.
  • ord returns a code point, so hashing is consistent for non-BMP characters, unlike charCodeAt in JavaScript.
  • Python's built-in hash() for strings is randomised per process (PYTHONHASHSEED) and is not usable for a rolling hash.
Common mistakes in this language
  • Slicing to verify (text[i:i+m] == pattern) in a hot loop instead of str.startswith(pattern, i), which allocates on every candidate.
  • Using the built-in hash() and expecting stability across runs.
  • Reaching for Rabin-Karp for a single-pattern search where str.find is both simpler and faster.
Language differences that matter here
  • Wide arithmetic again: Python needs nothing, JS/TS need BigInt, and C++ needs __int128 — and only for C++ does the choice of a Mersenne modulus enable a shift-based reduction that avoids division entirely.
  • Character units differ: Python ord yields code points, while JavaScript charCodeAt yields UTF-16 code units, so the two hash astral characters differently (consistently within each language, but not across them).
  • Verification without allocation: C++ string::compare(pos, len, other), JS/TS startsWith(pattern, i), Python str.startswith(pattern, i) — all three beat building a substring, and the Python version above deliberately shows the slower slice so the note can call it out.
  • Negative remainders need fixing in C++ and JS/TS and not in Python, the same split as everywhere else in modular arithmetic.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

O(n) preprocessing, then O(1) per substring hash. Probabilistic: equal hashes imply equal strings only with high probability.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Repeated substring-equality queries on a fixed string.
  • Binary search over a length with a duplicate/period check per length.
  • Palindrome queries on arbitrary substrings using forward and reverse hashes.
  • As a lighter alternative to Suffix Array or Suffix Tree when probabilistic answers are acceptable.
Avoid it when

Alternatives

Suffix ArrayKnuth–Morris–Pratt (KMP)Z-Algorithm

Common mistakes

  • Negative results from H[r] - H[l]·P[r-l] in languages where % keeps the sign — add M before reducing.
  • Overflow: H[l]·P[r-l] can reach M² ≈ 10^18, which fits in 64-bit but not if M is larger than about 3·10^9.
  • Using base B = 26 with characters mapped to 0..25 — a leading 'a' then contributes nothing and "a", "aa", "aaa" collide; map to 1..26 or use a larger base.
  • Comparing n² pairs with a single 32-bit modulus and getting bitten by the birthday paradox.

Interview patterns

  • Longest duplicate substring (binary search + hash set).
  • Count distinct substrings of each length.
  • Check if two substrings are anagram-free rotations, or whether s[i..j] is a palindrome, in O(1) per query.
  • Repeated DNA sequences with fixed-length windows.
Interview questions on this
Mock interviews

Example problems

Repeated DNA SequencesmediumLongest Palindromic Substringmedium