JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Rabin-Karp and Rolling Hashes

What if you could shrink a whole window of text down to a single number and compare numbers instead of letters? That is the idea behind rolling hashes, and it turns pattern matching into arithmetic you can slide across the text in O(1) per step.

From comparing letters to comparing numbers

The first guide in this rung weighed the cost of naive matching: at every one of the n - m + 1 alignments you re-compare up to m characters, for O(n*m) in the worst case. KMP and the Z-algorithm beat that by never re-reading a character they already understood. Rabin-Karp attacks the same problem from a completely different angle: instead of getting smarter about characters, it stops looking at characters one by one at all. It summarizes each m-length window of text as a single number and compares that number against the pattern's number.

The number is called a hash, or in this setting a fingerprint. The deal is irresistible: comparing two numbers is one operation, no matter how long m is, whereas comparing two strings of length m costs up to m operations. If we can compute the fingerprint of the pattern once, and the fingerprint of every text window cheaply, then most alignments are dismissed by a single integer comparison. The whole trick lives or dies on one question — can we get each window's fingerprint without re-reading all m of its characters?

The rolling-hash recurrence

Here is the clever part that gives the rolling hash its name. Treat each character as a digit in base b (think of b as the alphabet size, say 256), and read a window as a number in that base. The window c_0 c_1 ... c_(m-1) becomes the value c_0*b^(m-1) + c_1*b^(m-2) + ... + c_(m-1). Computing this from scratch costs O(m). But when the window slides one position to the right, the new value is almost the old one: we are just dropping the leftmost digit and appending a new rightmost digit, exactly like a car odometer rolling over.

H(window starting at i+1)
  = ( H(window at i) - text[i]*b^(m-1) ) * b  +  text[i+m]
         drop the leftmost digit, shift left one place, add the new digit
The roll: each slide of the window is a constant number of arithmetic operations, independent of m.

Subtract the contribution of the departing character (its digit times b^(m-1)), multiply the whole thing by b to shift every remaining digit up one place, then add the arriving character. That is a fixed handful of operations, so each slide is O(1) and computing all n - m + 1 window hashes takes O(n) total after an O(m) warm-up for the very first window. The value b^(m-1) is a constant we precompute once. This is the engine; everything else is bookkeeping to keep the engine honest.

Why we work modulo a prime

There is a problem hiding in the recurrence: b^(m-1) for a 256-letter alphabet and a pattern of length 50 is an astronomically large integer. Doing arbitrary-precision arithmetic on numbers that big would itself cost O(m) per operation and destroy the whole speedup. The fix is to do every computation modulo some fixed number M, so every value stays a single machine word. We pick M to be a large prime, and we usually pick the base b at random in the range 1 to M - 1.

Two reasons drive the choice of a prime modulus, both worth understanding rather than memorizing. First, modular arithmetic plays nicely here only because addition and multiplication commute with taking the remainder — (x*b + c) mod M can be computed step by step without ever forming the huge true value. Second, and deeper, choosing a prime M with a randomly chosen base spreads hash values evenly and lets us prove a small collision probability: the equation that two distinct windows collide becomes a polynomial equation modulo a prime, and a nonzero polynomial of degree m has at most m roots in that field. With M much larger than m, the chance of a random base hitting a root is tiny.

Collisions, and the two honest versions

Now we confront the lossiness head on. When a window's hash equals the pattern's hash, that is a CANDIDATE, not a confirmed match. A real match always produces equal hashes, so we never miss a true occurrence; but a different string can accidentally share the hash — a collision — and would be a false alarm if we trusted it blindly. There are two principled ways to handle this, and they sit on opposite sides of a classic trade-off introduced earlier in this ladder.

  1. Las Vegas (always correct): on every hash match, verify by comparing the actual m characters. A confirmed match is reported; a collision is discovered and discarded. The answer is always exactly right; only the running time is random, depending on how many spurious hash matches the verification has to clean up.
  2. Monte Carlo (always fast): trust every hash match as a real match and never verify. Each reported position is a true match unless a collision fooled us, so the algorithm runs in a guaranteed O(n + m) but may rarely report a false positive.

The verifying version is a Las Vegas algorithm; the unverified version is a Monte Carlo algorithm. With a single random prime modulus near 2^61 the probability that any particular collision survives is about m/M, vanishingly small, so the expected running time of the Las Vegas variant is O(n + m): the warm-up plus the slides plus an expected handful of verifications. The worst case, though, is still O(n*m) — if an adversary (or sheer bad luck) makes every window hash-match the pattern, every alignment triggers a full O(m) verification. Like randomized quicksort, the good bound is an EXPECTED bound, not a worst-case guarantee.

Where Rabin-Karp shines, and where it does not

If KMP gives a deterministic O(n + m) with no randomness and no false positives, why ever reach for Rabin-Karp? Because the rolling hash generalizes where prefix-function tricks do not. Searching for MANY patterns at once is the headline case: hash every pattern of a common length into a set, then slide one rolling hash across the text and look up each window in O(1) — far simpler to implement than Aho-Corasick when all patterns share a length. It also extends naturally to two-dimensional pattern matching (finding a small grid inside a big one), which the linear string methods do not handle gracefully.

The rolling fingerprint is also reusable machinery beyond matching. Hashed substrings let you answer 'are these two ranges of the text equal?' in O(1) after O(n) preprocessing, a building block in many competitive-programming and bioinformatics tasks, and the modular arithmetic underneath is exactly the fast modular exponentiation world you met in the number-theory rung. Comparing fingerprints to test equality is, conceptually, the same idea as a randomized primality test such as Miller-Rabin: replace an expensive exact check with a cheap probabilistic one that is wrong only with controllably tiny probability.

Be honest about the costs, though. Rabin-Karp's elegance rides on assumptions: that arithmetic on a machine word is O(1) (a single mod prime ignores the cost of huge numbers, which is exactly why we use it), and that the input is not adversarially crafted against your fixed parameters. A determined adversary who knows your base and modulus can engineer worst-case collisions, which is why the random choice of base must stay secret to enjoy the expected bound. For a single small pattern with no such concerns, KMP or the Z-algorithm are usually the cleaner, dependency-free choice; Rabin-Karp earns its keep when many patterns, range-equality queries, or higher dimensions enter the picture.