Rabin-Karp and Rolling Hashes, Explained

The Rabin-Karp algorithm finds occurrences of a pattern inside a longer string by comparing hash values instead of characters directly. Its key trick is a rolling hash — a hash function that can be updated in constant time as a search window slides one character forward, rather than being recomputed from scratch. That makes Rabin-Karp especially good at one specific job: searching for many patterns in the same text, or the same pattern across many texts, cheaply.

The naive approach and why it’s slow

The brute-force way to find a pattern of length m inside a text of length n is to check every possible starting position: slide a window across the text and compare it to the pattern character by character. In the worst case — long strings of near-matches — this costs O(n·m) time, since each of the n - m + 1 positions can require up to m comparisons before a mismatch is found.

Rabin-Karp’s idea is to avoid comparing characters most of the time. Instead, compute a numeric hash of the pattern once, then compute a hash of every m-length window in the text and compare hashes. If the hashes differ, the substrings can’t match, and you move on. If the hashes match, you do a direct character comparison to rule out a false positive (a hash collision).

The rolling hash trick

Hashing every window from scratch would cost O(m) per position, giving no improvement over brute force. The rolling hash is what makes this fast: it lets you compute the hash of the next window using only the hash of the current window, in O(1) time.

A common construction treats each substring as a number in some base b (larger than the alphabet size), reducing modulo a large prime q to keep the numbers bounded. For a window starting at position i:

hash(s[i..i+m]) = (s[i]·b^(m-1) + s[i+1]·b^(m-2) + ... + s[i+m-1]) mod q

To slide the window forward by one character, you subtract the contribution of the outgoing character, multiply by b, and add the incoming character:

new_hash = ((old_hash - s[i]·b^(m-1)) · b + s[i+m]) mod q

Because b^(m-1) mod q is a fixed constant computed once up front, this update is a handful of arithmetic operations — no matter how long the window is. That’s the whole trick: the cost of hashing a window drops from O(m) to O(1) amortized across the scan, bringing the average-case total to O(n + m).

Worst case vs average case

Rabin-Karp’s worst case is still O(n·m) — if the hash function collides often (or an adversary picks input designed to collide), you fall back to verifying every window character by character. In practice, with a well-chosen modulus and base, collisions are rare enough that the algorithm behaves close to its O(n + m) average case. This is a common pattern in hashing: the data structure or algorithm is fast on average and only degrades under pathological or adversarial input, similar to how a poorly distributed hash table degrades toward linked-list performance under heavy collisions.

Rabin-Karp vs KMP

The Knuth-Morris-Pratt (KMP) algorithm is the other classic answer to single-pattern string search, and it guarantees O(n + m) in the worst case — no collision risk, because it works by precomputing how much of the pattern can be reused after a partial match, rather than hashing anything.

	Rabin-Karp	KMP
Core idea	Compare rolling hashes	Reuse partial-match information via a prefix table
Worst case	O(n·m) (rare with good hashing)	O(n + m) guaranteed
Multiple patterns	Extends naturally (hash each pattern)	Needs a separate structure (e.g., Aho-Corasick)
Simplicity	Simple arithmetic, easy to extend	More intricate preprocessing step

The practical dividing line: reach for KMP when you need an ironclad worst-case guarantee for single-pattern search. Reach for Rabin-Karp when you need to search for many patterns at once — because hashing generalizes cleanly to comparing a set of pattern hashes against each window, something KMP doesn’t do without extra machinery.

Where rolling hashes show up beyond string search

The rolling hash idea outlives the search algorithm it was named for:

• Plagiarism and duplicate detection — hashing overlapping windows of text (or code) to spot near-identical passages without an exact diff.
• Content-defined chunking — backup and deduplication tools use rolling hashes to decide where to split a file into chunks, so that small edits only change the chunks near the edit rather than shifting every following byte.
• The rsync algorithm — computes rolling checksums over blocks to find which parts of a file changed since the last sync, transferring only the differences.
• Bloom filters and count-min sketches — related hashing-based structures that trade a small false-positive rate for large memory savings; see what a Bloom filter is and what a count-min sketch is for the broader family.

The takeaway

Rabin-Karp turns substring search into a hash comparison problem, and the rolling hash is what keeps that cheap — updating a window’s hash in constant time as it slides, instead of recomputing from scratch. Its average-case performance matches KMP’s guaranteed worst case, and it generalizes more easily to searching for many patterns at once, which is exactly why the rolling hash technique shows up well beyond pattern matching, from file synchronization to deduplication.