Polynomial Rolling Hashes and the Rabin-Karp Trade

Comparing two strings of length m costs m character comparisons. A matcher that does this at every one of n−m+1 alignments performs Θ(nm) work, and the work is unavoidable if the comparison is character by character. The alternative is to compare a fixed-size number computed from each window, so that the comparison is one machine instruction and the number for the next window can be derived from the previous one rather than recomputed. Rabin and Karp built a pattern matcher on exactly that substitution.

A hash that can be updated in one step

Treat a window of m characters as the coefficients of a polynomial and evaluate it at a fixed base b modulo a fixed number:

h(s) = (s[0]·b^(m-1) + s[1]·b^(m-2) + ... + s[m-1]) mod p

Moving the window one position drops s[0], shifts every remaining coefficient up by one power, and appends the new character. In modular arithmetic that is

h' = (h - s[0]·b^(m-1))·b + s[m]  (mod p)

provided b^(m-1) mod p is precomputed once. Each step is a subtraction, a multiplication, an addition, and two reductions. The window hash is no longer recomputed from m characters; it is carried forward, so the scan is Θ(n) hash updates plus one full comparison whenever a hash matches.

The precomputation matters: b^(m-1) mod p can be obtained by fast exponentiation in O(log m) multiplications, or by multiplying b m−1 times. Either is negligible against the scan.

Why a match must be verified

A hash of m characters into a modulus p has p possible values and |Σ|^m possible inputs, so for m large enough to exceed log p the map cannot be injective. Two different windows can share a hash, and a matcher that trusts the hash reports a false match. The standard fix is to verify every candidate by direct comparison. Verification costs O(m) for each hash hit, so the total is O(n + h·m) where h is the number of hits. On random text with a large modulus, h is close to the number of true occurrences and the scan is effectively linear. On degenerate input — a text of one repeated character, a pattern of the same character — every alignment is a true occurrence rather than a false one, so the scan reports n−m+1 matches and each verification scans the full m characters; producing the output alone costs that much, and any matcher that reports every occurrence pays it. What separates Rabin–Karp from the prefix-function method is a different input: text whose windows collide without matching. Rabin–Karp’s expected cost on that input depends on the modulus, its worst case is Θ(nm), and the bound holds in expectation over the choice of base rather than for every input, which is a weaker guarantee than the prefix-function method described in the prefix function and linear-time matching.

The collision probability is the quantity that determines whether the expected bound is meaningful. For a fixed pair of distinct strings and a randomly chosen base, the difference polynomial has degree below m and at most m−1 roots, so at most m−1 of the p possible bases produce a collision. The probability is at most (m−1)/p. With p near 2^61 and m in the thousands, the probability for one window is on the order of 10^-15, and the expected number of false hits across a scan of n windows is about n·m/p, which is a fraction of one for any realistic n.

That argument requires the base to be random and the modulus to be prime. Both conditions are routinely dropped, and dropping them is where implementations break.

Modulus choices and what they cost

Three arithmetic regimes are common, and they differ in speed, portability, and adversarial resistance.

A machine word with wraparound. Using 64-bit unsigned arithmetic with no explicit reduction is the fastest option: the compiler emits a multiply and the overflow is the modulus, effectively p = 2^64. It is also the weakest. The ring of integers modulo 2^64 is not a field, and a polynomial over it has far more roots than degree suggests; worse, an adversary who knows the base can construct strings that collide by solving a linear system over the ring, which is practical for a fixed base and a small alphabet. The regime is acceptable only for non-adversarial input such as checksums over data the program itself produced.

A large prime below the word size. The usual choice is 2^61−1, a Mersenne prime, because reduction modulo it can be done with a shift, an add, and a conditional subtraction rather than a division. Multiplication of two 61-bit values produces a 122-bit product, which needs a 128-bit intermediate type or a manual split into halves. On 64-bit hardware the whole update is a handful of instructions with no divide, which is why this modulus is popular in performance-sensitive code.

A small prime with 32-bit arithmetic. Values such as 10^9+7 keep every intermediate in 64 bits and port cleanly to languages without unsigned overflow semantics. The collision probability per comparison rises to roughly m/p ≈ 10^-6 for m in the thousands, which is too high to ignore on long texts; the usual remedy is two different primes, giving a combined probability near the product.

Modulus	Reduction cost	Collision bound per comparison	Adversarial safety
2^64 wraparound	free	no useful bound	none
2^61−1	shift and add	≈ m/2^61	good with random base
10^9+7	division or Barrett	≈ m/10^9	good with random base
two small primes	two reductions	product of the two bounds	good

Double hashing doubles the update cost and does not change the asymptotics. It is worth it when the input is untrusted and a single collision would be a correctness failure rather than a slowdown.

The base is part of the contract

A fixed base turns the hash into a public function, and a public function can be inverted. The attack is constructive rather than statistical: given the base and modulus, an adversary writes down the linear relation that a collision must satisfy and solves for a pair of strings. Randomising the base at program start from a source the adversary cannot predict restores the probabilistic argument. Randomising per string, or per query, removes the attack entirely at the cost of not being able to compare hashes across calls.

Two bases are structurally bad regardless of randomness. Base 1 makes every string of a given length hash to the sum of its characters, so any anagram collides. A base equal to 0 mod p contributes nothing to the polynomial, so every string hashes to its last character whatever its length. Implementations pick bases larger than the alphabet, commonly a large odd constant, and the choice is otherwise arbitrary.

Character encoding is a second hidden decision. Hashing bytes of a UTF-8 string and hashing code points of the same string give different values, and a window that starts mid-sequence hashes something that is not a character. For matching purposes the hash must be computed over the same units the matcher reports offsets in.

Where the rolling property is the point

Rabin–Karp as a pattern matcher is rarely the fastest choice; the prefix function has a stronger worst-case bound and Boyer–Moore’s skip heuristics are faster on natural language. The rolling hash earns its place in problems where the comparison is not against a fixed pattern but between many substrings of the same text.

Longest repeated substring and the longest common substring of two texts reduce to comparing windows against each other. With prefix hashes over the whole text, the hash of any substring is available in O(1) as H[r] − H[l]·b^(r−l), and binary search over length answers both questions in O(n log n) hash computations instead of a suffix-structure construction. Counting distinct substrings does not reduce the same way: the quantity is a count rather than a comparison, and answering it with hashes means inserting every one of the Θ(n²) windows into a table, which is quadratic even when each insertion is constant. The answers the rolling hash does give are probabilistic in the same sense as the matcher: a collision produces a wrong length, and verification of the final candidate is the usual guard.

M = (1 << 61) - 1
BASE = 911382323

def reduce_mod(x):
    # Fold modulo the Mersenne prime 2^61-1 without a division.
    x = (x & M) + (x >> 61)
    return x - M if x >= M else x

def build(s):
    prefix = [0] * (len(s) + 1)
    power = [1] * (len(s) + 1)
    for i, ch in enumerate(s):
        prefix[i + 1] = reduce_mod(prefix[i] * BASE + ord(ch))
        power[i + 1] = reduce_mod(power[i] * BASE)
    return prefix, power

def subhash(prefix, power, l, r):
    # Hash of s[l:r] as an independent polynomial.
    return reduce_mod(prefix[r] - reduce_mod(prefix[l] * power[r - l]))

The fold in reduce_mod is the reason this modulus is used: x >> 61 recovers the overflow above 2^61, and adding it back is congruent to subtracting a multiple of 2^61−1 because 2^61 ≡ 1. Written as (x & M) + (x >> 61), the result is at most (2^61−1) + (2^61−1), so one conditional subtraction finishes the job. Omitting the x >> 61 term would truncate rather than reduce, which silently changes the hash and makes two implementations that appear to use the same modulus disagree. The same trap exists in C, where the 122-bit product of two 61-bit values must be folded from a 128-bit intermediate explicitly.

Failure modes worth naming

Empty patterns are a caller-side edge case: every alignment matches the empty string, so a matcher either rejects them before computing the hash or reports n+1 zero-width occurrences, and the choice belongs to the interface rather than to the arithmetic. Windows shorter than the pattern cannot be compared. Text shorter than the pattern produces no hits and must not underflow the index arithmetic. In languages where array indexing is signed, the expression i - m + 1 at the first hit is the boundary to check.

Hash values are not order-preserving, so a rolling hash cannot replace a suffix array for lexicographic queries; it answers equality only. For ordering, the structures in suffix array construction and LCP do the job. For multi-pattern matching, hashing every pattern separately scales with the number of patterns, whereas Aho–Corasick failure links shares the scan across all of them.

Finally, the rolling hash is a fingerprint, not a checksum with error-detecting properties. A single bit flip in the input changes the hash unpredictably, which is desirable for equality testing and useless for diagnosing where two strings differ.