Rabin-Karp & Rolling Hashes

In short: Rabin-Karp fingerprints every window with a polynomial hash, so comparing two windows is one number comparison instead of m character comparisons. Sliding the window removes the leaving character's weight, shifts, and adds the entering character, all in O(1), so the whole scan is O(n + m) expected. A hash match is only a hint — two different windows can collide — so every hit must be verified against the real characters before it counts as a match.

A window "41" sliding to "18": drop the leaving 4's weight, shift, add the entering 8

From here on, the course builds Quarry, a small search-and-storage engine: the kind of program that sits under a log viewer, a code-search box or a document store. Each section adds one subsystem, and this one adds the text index. A user types a phrase, and Quarry says where it occurs in a pile of text without reading any character more often than it has to.

The first question is the obvious one. How do you find a pattern of length m inside a text of length n?

The naive search, and where it wastes work

Line the pattern up at every start position and compare character by character until something differs:

python

On ordinary English the inner loop usually stops at the first character, so the search is close to O(n). On repetitive text it is not. A thousand as and a pattern of twenty as then a b make every alignment compare 21 characters before failing, which is about n · m comparisons. Machine logs, DNA and padded records are exactly that kind of repetitive.

What does this print?

text, pattern = "aaaaa", "aab"
compares = 0
for i in range(len(text) - len(pattern) + 1):
    for j in range(len(pattern)):
        compares += 1
        if text[i + j] != pattern[j]:
            break
print(compares)

Compare numbers, not strings

Rabin and Karp's idea is to give every window a fingerprint, a single number computed from its characters. Work out the pattern's fingerprint once. Then, at each alignment, compare two numbers instead of m characters. Only when the numbers agree do you look at the characters, to confirm.

That only pays off if two conditions hold:

different strings usually get different fingerprints, and
the next window's fingerprint can be found from the current one in O(1), without rereading the whole window.

A polynomial hash gives both. Treat the string as a number written in base B, with each character's code as a digit, and keep only the remainder modulo M:

h(s) = \left(s_0 B^{m-1} + s_1 B^{m-2} + \cdots + s_{m-1}\right) \bmod M

Horner's rule computes it left to right with one multiply and one add per character:

python

Step through the same loop on a three-letter word and watch h grow and wrap:

step through it

1h = 0

2for ch in "cab":

3 h = (h * 256 + ord(ch)) % 101

4print(h)

❓ Cross-question — "Why not just add the character codes?" Because a sum ignores order. "cat" and "act" would collide, and so would every anagram. The powers of B give each position its own weight, the way the digits of 472 and 274 mean different amounts.

Rolling the window

Here is the payoff. When the window slides one place right, one character leaves at the front and one enters at the back. In base 10 with the window 41 about to become 18:

remove the leaving digit's contribution: 41 − 4·10 = 1
shift everything one place left: 1 · 10 = 10
add the entering digit: 10 + 8 = 18

The same three moves work on the remainder, because taking mod M after each step never changes the final remainder:

h_{i+1} = \big((h_i - s_i \cdot B^{m-1}) \cdot B + s_{i+m}\big) \bmod M

B^{m-1} mod M is computed once, before the scan, so each slide costs O(1) whatever the pattern's length.

Below, the text is a string of digits and the base is 10, so you can check every fingerprint in your head. The modulus is a deliberately tiny 7, which makes collisions common enough to see:

watch it move · array

Each slide updates the fingerprint in O(1). Characters are compared only on a hash hit, and a hit can still be a false alarm.

The pattern 27 has fingerprint 6. The first window, 41, has 41 mod 7 = 6 too. That's a hash hit, so now the characters get compared. 10 cells. i at index 0.

pattern 27 → 27 mod 7 = 6

1 / 9

What does this print?

base, mod = 10, 7
h = 41 % mod                              # window "41"
h = ((h - 4 * base) * base + 8) % mod     # drop the 4, bring in the 8
print(h, 18 % mod)

Rabin-Karp in full

Put the pieces together. Hash the pattern and the first window, then slide. On a hit, verify with a slice comparison:

python

pow(base, m - 1, mod) is Python's three-argument power. It reduces modulo mod as it goes, so it never builds a huge number.

This version loses a match. Find why:

broken — fix it

"abra" occurs at 0 and at 7, but this prints only [0]. The second one is the last window.

Now run your own. The code below redraws the window as it slides, marking hits in green and false alarms in red. Change mod from 7 to 13, then to 101, and watch the false alarms disappear. Then try a text of your own:

your code, drawn · array

Your rolling hash, one slide per frame. Every frame costs O(1) work, and only a hit costs a character comparison.

Choosing the modulus

A false alarm costs one wasted verification. The danger is a modulus that makes false alarms systematic rather than rare. Watch what happens when the modulus shares a factor with the base:

python

With M = 256 = B, every power of B from B¹ up is 0 mod M, so only the last character survives and every word ending in t collides. A modulus that divides some power of the base throws information away the same way. Here is the short number-theory note behind the usual choice:

Pick a prime M that doesn't divide B. Then B has an inverse mod M, the powers of B never collapse to 0, and each position keeps its own weight.
Pick M large. For two fixed different strings, the chance that a random-ish hash makes them collide is roughly 1/M. Over n windows you expect about n/M false alarms.
Pick B larger than the alphabet. With B = 256, two different byte strings of the same length are different base-256 numbers before the modulus touches them.
Against an adversary, randomise. Someone who knows B and M can construct colliding strings. Choosing B at random when Quarry starts, or keeping two hashes with different primes, defeats that. With two, a false alarm needs both to collide at once.

Quarry scans a million windows, and about n/M of them collide by accident. That's 1,000 false alarms with $M = 10^3$ , one with $M = 10^6$ , and 0.1 with $M = 10^7$ , the first power of ten that gets below one. Real engines use a prime near $10^9$ , or two primes at once, which makes a false alarm about a one-in-a-billion event per window.

❓ Cross-question — "Python has hash(). Why not use that?" It's fine inside one run for a dict, but it can't roll: you'd rehash the whole window every time. On top of that, string hashing is salted per process, so the same text hashes differently tomorrow. A fingerprint that Quarry writes to disk must be one you define yourself.

An interview question: shared runs of events

Two services each log a sequence of event codes, one character per event. Does any run of k consecutive events appear in both logs?

Comparing every run in one log with every run in the other is O(n · m · k). Fingerprint every window of the first log into a set, then roll through the second and check membership. A hit still needs verifying, so keep the start positions next to each fingerprint:

python

That is O(n + m) expected time. The build and boss exercises below use the same set-of-fingerprints move.

What it costs

	naive	Rabin-Karp
preprocessing	none	O(m) to hash the pattern
each alignment	up to O(m)	O(1) update, plus O(m) on a hit
whole scan, typical	O(n)	O(n + m) expected
whole scan, worst case	O(n · m)	O(n · m) if nearly every window really matches
extra memory	O(1)	O(1)

The worst case survives because real matches still have to be verified. Search "aaa" in a million as and there are nearly a million genuine hits to confirm. What Rabin-Karp removes is the cost of the windows that don't match, and those are almost all of them. The next lesson removes the worst case entirely, with no hashing at all.

Idioms & real-world patterns

pow(base, m - 1, mod) for the leaving character's weight. Compute it once.
Hash, then verify. Equal fingerprints mean probably equal strings, never certainly. Always confirm before reporting a match.
A dict from fingerprint to start positions turns "does any window repeat?" into one pass.
Where rolling hashes live: duplicate-file and plagiarism detection, the chunk boundaries in backup tools and rsync, repeated-substring searches, and anywhere many patterns of the same length are searched at once (hash them all into one set).

Quick practice

What does this print?

def h(s, base, mod):
    v = 0
    for ch in s:
        v = (v * base + ord(ch)) % mod
    return v

print(h("cab", 10, 97), h("bac", 10, 97))

broken — fix it

"27" doesn't occur anywhere in "6207318", but this reports hits at [0, 1] — both are false alarms under the tiny modulus 7, reported as real because nothing verifies them.

🎯 Your turn

Build hash_scan(text, pattern, mod), Quarry's fingerprint scanner. Use base 256 and character codes, h(s) = (ord(s₀)·256^(m−1) + … + ord(s_{m−1})) mod mod, and roll the window across text. Return a dict:

"matches": the start index of every real occurrence, in order (overlaps count)
"false_hits": how many windows had the pattern's hash but different characters

If the pattern is empty or longer than the text, return {"matches": [], "false_hits": 0}.

hash_scan("abracadabra", "abra", 1_000_003) → {"matches": [0, 7], "false_hits": 0}
with a tiny modulus like 3, some windows will collide, so "false_hits" goes up.

Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.

Rabin-Karp & Rolling Hashes

Rabin-Karp & Rolling Hashes

The naive search, and where it wastes work

Compare numbers, not strings

Rolling the window

Rabin-Karp in full

Choosing the modulus

An interview question: shared runs of events

What it costs

Idioms & real-world patterns

Quick practice

🎯 Your turn

Practice — level up