Rabin-Karp: Searching Text With a Rolling Hash

Comparing numbers instead of characters

The naive way to find a pattern of length m inside a text of length n is to try every starting position and compare character by character: O(n*m) in the worst case. Rabin and Karp's 1987 trick is to hash the pattern once and hash every m-length window of the text, then compare cheap integers instead of expensive strings. Two windows can only possibly be equal if their hashes are equal, so almost every position is eliminated with a single integer comparison.

The polynomial rolling hash

The hash treats a string of characters as digits of a number in some base b, reduced modulo a prime q so it fits in a machine word:

H(s0 s1 ... s(m-1)) = ( s0*b^(m-1) + s1*b^(m-2) + ... + s(m-1) ) mod q

This is exactly how you'd compute the decimal value of a string of digits, just in base b with characters as digit values and everything wrapped modulo q so the numbers never overflow.

Sliding the window in O(1)

The polynomial form is chosen specifically so a window's hash can be updated incrementally instead of recomputed from scratch. Moving the window one character to the right removes the leading digit's contribution, shifts every remaining digit up one place, and adds the new trailing digit:

// text[i..i+m-1] -> text[i+1..i+m], b^(m-1) precomputed once
h = ( (h - text[i] * bPow) * b + text[i + m] ) mod q;
if (h < 0) h += q;   // keep the remainder non-negative

One multiply, one subtract, one add, one modulo — the same constant cost no matter how long the pattern is. That is the entire reason Rabin-Karp exists: a naive rehash of every window would cost O(m) per shift, erasing the benefit of hashing altogether.

Base, modulus, and the collisions that don't go away

A hash match is a candidate, never proof. Different strings can collide onto the same value modulo q, so a real implementation always verifies a hash hit character by character against the pattern before reporting a match — the false positives that slip through are rare enough that this verification step costs almost nothing on average. Picking q as a large prime and b as a value not tied to the alphabet size (or randomizing b at run time) keeps an adversary from constructing text that collides on purpose; using two independent hashes in parallel makes accidental collisions negligible.

Average O(n+m), worst case O(n*m)

With a good hash, almost every window's hash differs from the pattern's, so the expected running time is O(n + m): one pass to hash the text, a handful of O(m) verifications for the rare true and false matches. The worst case is still O(n*m), reached only if an adversary forces mass collisions — which is why algorithms like Knuth-Morris-Pratt or the Z-algorithm, both O(n+m) worst case with no randomness involved, are preferred when a guarantee matters more than simplicity. Rabin-Karp's advantage shows up elsewhere: because two hashes of the same length are always directly comparable, it generalizes effortlessly to searching for many patterns at once by hashing them all into a lookup set.

Beyond text search

The same sliding-window hash underlies tools far outside string matching. Plagiarism and duplicate-content detectors hash overlapping k-grams of a document to fingerprint it cheaply. Content-defined chunking in rsync and deduplicating backup systems uses a rolling hash to decide chunk boundaries so that inserting a byte near the start of a file doesn't shift every chunk boundary after it — only the chunks actually touched change. Any place you need to detect a moving pattern inside a stream without rescanning everything from scratch is a candidate for the same trick.

Frequently asked questions

Try it live

Everything above runs in your browser — open Rabin-Karp and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.