Rabin-Karp rolling hash

What this chapter covers

KMP searched by comparing characters cleverly. Rabin-Karp does something completely different: it compares numbers. Hash the pattern into a single integer, then slide a window across the text hashing each length-m window into an integer too, and wherever the window's number equals the pattern's number, you've probably found a match — a quick character check confirms it. Comparing two integers is one operation regardless of how long the strings are, so the search is fast if you can compute each window's hash cheaply. The magic that makes it cheap is a rolling hash: when the window slides one character right, you update its hash in constant time instead of recomputing it from scratch. This chapter builds the rolling hash, shows why the modulus makes collisions astronomically rare, and demonstrates Rabin-Karp's genuine superpower — searching for hundreds of patterns in a single pass, where KMP would sweep the text once per pattern. In the face-off, that's 200 times faster.

A bit of history

Michael Rabin and Richard Karp introduced the algorithm in 1987, and its significance was less about raw speed for one pattern — KMP already had that — than about a new idea: randomization and hashing applied to string matching. Rabin was one of the founders of the theory of randomized algorithms (his work on probabilistic primality testing is from the same era), and Rabin-Karp is a beautiful small example of the philosophy: accept a vanishingly small probability of error (a hash collision) in exchange for simplicity and a capability the deterministic algorithms lack. The rolling-hash technique they used turned out to be one of the most reusable ideas in all of computing — the same fingerprinting trick powers rsync's delta transfer, content-defined chunking in backup and deduplication systems, plagiarism detectors, and Git's diff heuristics. Rabin-Karp is where most people first meet the rolling hash, and the rolling hash outgrew the algorithm.

The intuition

Assign every character a numeric value and read a string as a number in some base — "abc" becomes, say, a·B² + b·B + c for a base B. That's a polynomial hash, and two different strings almost always produce different numbers (we reduce modulo a large prime to keep the numbers bounded, which is the only source of possible collisions). Now the naive plan is clear: compute the pattern's hash once, and for each window of the text compute that window's hash and compare. But computing a window's hash from scratch costs O(m), and there are n windows, so that's O(n·m) — no better than naive matching.

The rolling hash removes the waste. Look at two adjacent windows: they share all but one character on each end. When the window slides right by one, the leftmost character leaves and a new character joins on the right. Its hash changes in a predictable, O(1) way: subtract the leaving character's contribution (its value times the base raised to the window length), multiply the rest by the base to shift everyone up a place, and add the new character. One subtraction, one multiply, one add — the hash of the next window from the hash of the current one, without looking at the m−2 characters in the middle. So each window costs O(1) to hash, the whole scan is O(n), and matching is O(n+m) expected. On a hash match you do one honest character comparison to rule out the rare collision, and you're done.

Complexity: how it scales

Rabin-Karp is $O(n + m)$ expected: $O(m)$ to hash the pattern and first window, then $O(1)$ per slide for $n$ windows, plus verification cost that's negligible when collisions are rare. Its worst case is $O(n \cdot m)$ — if an adversary engineers many hash collisions, every window triggers a full character verification — but with a good random-ish modulus that's astronomically unlikely on real input (the correctness test ran two thousand searches with zero spurious collisions). For a single pattern, this is no better asymptotically than KMP, and in practice slower, since KMP is deterministic and doesn't hash. Rabin-Karp's real advantage appears with many patterns, which is what the face-off measures — searching k patterns of the same length, Rabin-Karp in one pass versus KMP run k times:

For a single pattern the two are comparable (KMP even edges ahead, being deterministic). But watch what happens as the pattern count grows: KMP's time climbs linearly with k, because it must sweep the whole 200,000-character text once for every pattern, while Rabin-Karp sweeps the text once and checks each window's hash against a set of all k pattern hashes in O(1). At 800 patterns, Rabin-Karp finished in about 29 ms and KMP-per-pattern took 5.8 seconds — 200 times faster. That's the payoff of turning strings into numbers: a number can be looked up in a hash set, so one pass answers "does this window match any of my patterns?" as cheaply as it answers "does it match this one?"

What it's good at, what it isn't

Rabin-Karp shines wherever hashing a window pays off across many comparisons. Its headline use is multi-pattern search: virus scanners, intrusion-detection signatures, and spam filters that hunt for many fixed strings at once check each text window's hash against a set of pattern hashes in one pass. It extends naturally to two-dimensional pattern matching (finding an a×b image patch in a larger image, by hashing rows then columns), which KMP doesn't do gracefully. And the rolling hash on its own — independent of the search — is the workhorse of fingerprinting: rsync and backup systems find matching blocks between files by rolling a hash to locate shared chunks; plagiarism and duplicate-detection tools fingerprint overlapping substrings; Git uses rolling-hash ideas in its diff and packing. Learning Rabin-Karp is really learning the rolling hash, which is the more valuable prize.

Where Rabin-Karp is the wrong tool is single-pattern exact search over adversarial or untrusted input, where its probabilistic nature and worst-case quadratic are liabilities KMP and Boyer-Moore avoid. Its equal-length requirement for multi-pattern search is a real constraint (patterns of different lengths need one rolling hash per length, or a different structure), and for large or dynamic pattern sets the right tool is Aho-Corasick (a later chapter), which builds a single automaton for all patterns of any lengths. And in everyday single-pattern code you'd just call str.find. Rabin-Karp's niche is many-patterns, multi-dimensional, and fingerprinting — not beating KMP at its own one-pattern game.

The data, or the inputs

The face-off searches a 200,000-character random text for a growing number of length-8 patterns, timing Rabin-Karp's single multi-pattern pass against running KMP once per pattern. Correctness is checked two ways: on two thousand random searches Rabin-Karp's matches must equal Python's str.find (and the run reports how many spurious collisions occurred — zero, confirming the modulus), and the multi-pattern search must agree with running KMP on each pattern separately. The animation runs a single-pattern search of abc in aabbaabca using a deliberately tiny modulus (101) so the hash numbers are small and readable — real code uses a huge prime, but the small one shows the rolling arithmetic clearly.

Build it, one function at a time

The rolling hash and the single-pattern search — hash once, then roll in O(1):

def _hash(s):
    """The polynomial hash of a whole string: s[0]*BASE^(m-1) + ... + s[m-1], mod MOD. This is
    the string read as a big base-256 number, reduced modulo a prime to keep it bounded."""
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h


def rabin_karp(text, pattern):
    """Find every occurrence of `pattern` in `text` with a rolling hash. Hash the pattern and
    the first window once; then slide, updating the window hash in O(1) each step; on a hash
    match, VERIFY the characters (to rule out the rare collision). O(n+m) expected. Returns
    (matches, spurious) where `spurious` counts hash matches that failed verification — the
    collisions the modulus is chosen to make vanishingly rare."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    high = pow(BASE, m - 1, MOD)                 # BASE^(m-1): the weight of the leftmost char
    ph = _hash(pattern)
    wh = _hash(text[:m])                         # hash of the first window
    matches, spurious = [], 0
    for i in range(n - m + 1):
        if wh == ph:                             # numbers agree → probable match
            if text[i:i + m] == pattern:         # confirm with a real character comparison
                matches.append(i)
            else:
                spurious += 1                    # a hash collision, not a real match
        if i < n - m:                            # roll the window forward by one, in O(1)
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return matches, spurious

And the superpower — many patterns in a single pass, via a set of pattern hashes:

def rabin_karp_multi(text, patterns):
    """Rabin-Karp's superpower: search for MANY patterns of the same length in a single pass.
    Hash every pattern into a dict (hash → patterns), then roll one hash across the text and,
    at each window, look up its hash in the dict — O(1) — verifying any candidates. One sweep
    of the text finds all k patterns, where running a single-pattern search k times would sweep
    it k times. Returns {pattern: [positions]}."""
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns), "multi-search needs equal-length patterns"
    by_hash = {}
    for p in patterns:
        by_hash.setdefault(_hash(p), []).append(p)
    n = len(text)
    found = {p: [] for p in patterns}
    if m > n:
        return found
    high = pow(BASE, m - 1, MOD)
    wh = _hash(text[:m])
    for i in range(n - m + 1):
        if wh in by_hash:                        # this window matches some pattern's hash
            window = text[i:i + m]
            for p in by_hash[wh]:
                if window == p:
                    found[p].append(i)
        if i < n - m:
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return found

Watch it work

Here's Rabin-Karp searching for abc in aabbaabca, using a toy hash (each letter is a small digit, modulus 101) so you can read the numbers. The pattern abc hashes to 22. The blue window slides across the text one character at a time; each step, the green character is the one that just entered on the right and the red character is the one that just left — the only two the rolling hash needs to update the number in O(1). Watch the window's hash change with each roll, compared against 22. Most windows don't match and roll straight on; when the window over abc finally hashes to 22, a quick character check confirms it's a real match, not a collision, at position 5. The middle characters of the window are never re-read — that's the whole point of rolling:

The complete code

The from-scratch tab is Rabin-Karp — rolling hash, single-pattern search, and the multi-pattern pass; the library tab is KMP from last chapter, used both to check correctness and as the per-pattern cost in the face-off, plus the str.find reference. Flip between them.

"""Rabin-Karp — substring search by HASHING. KMP compared characters; Rabin-Karp compares
numbers. Turn the pattern into a single number (a hash of its characters), then slide a
window across the text turning each length-m window into a number too, and wherever the
window's number equals the pattern's number, you've probably found a match — verify it
character by character to be sure. Comparing two integers is O(1), so if you can compute each
window's hash cheaply, the whole search is fast.

The trick that makes it cheap is a ROLLING HASH: when the window slides one character right,
you don't recompute its hash from scratch (that would be O(m) per window, O(n·m) overall).
Instead you update it in O(1) — subtract the contribution of the character leaving on the
left, shift, and add the character entering on the right. That's the whole idea, and it has
a superpower KMP lacks: to search for MANY patterns of the same length at once, you hash the
text windows just once and check each against a whole SET of pattern hashes.
"""

BASE = 256          # treat the string as a base-256 number (one byte per char)
MOD = (1 << 61) - 1  # a large Mersenne prime → collisions astronomically unlikely


# region: rolling_hash
def _hash(s):
    """The polynomial hash of a whole string: s[0]*BASE^(m-1) + ... + s[m-1], mod MOD. This is
    the string read as a big base-256 number, reduced modulo a prime to keep it bounded."""
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h


def rabin_karp(text, pattern):
    """Find every occurrence of `pattern` in `text` with a rolling hash. Hash the pattern and
    the first window once; then slide, updating the window hash in O(1) each step; on a hash
    match, VERIFY the characters (to rule out the rare collision). O(n+m) expected. Returns
    (matches, spurious) where `spurious` counts hash matches that failed verification — the
    collisions the modulus is chosen to make vanishingly rare."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    high = pow(BASE, m - 1, MOD)                 # BASE^(m-1): the weight of the leftmost char
    ph = _hash(pattern)
    wh = _hash(text[:m])                         # hash of the first window
    matches, spurious = [], 0
    for i in range(n - m + 1):
        if wh == ph:                             # numbers agree → probable match
            if text[i:i + m] == pattern:         # confirm with a real character comparison
                matches.append(i)
            else:
                spurious += 1                    # a hash collision, not a real match
        if i < n - m:                            # roll the window forward by one, in O(1)
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return matches, spurious
# endregion


# region: multi
def rabin_karp_multi(text, patterns):
    """Rabin-Karp's superpower: search for MANY patterns of the same length in a single pass.
    Hash every pattern into a dict (hash → patterns), then roll one hash across the text and,
    at each window, look up its hash in the dict — O(1) — verifying any candidates. One sweep
    of the text finds all k patterns, where running a single-pattern search k times would sweep
    it k times. Returns {pattern: [positions]}."""
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns), "multi-search needs equal-length patterns"
    by_hash = {}
    for p in patterns:
        by_hash.setdefault(_hash(p), []).append(p)
    n = len(text)
    found = {p: [] for p in patterns}
    if m > n:
        return found
    high = pow(BASE, m - 1, MOD)
    wh = _hash(text[:m])
    for i in range(n - m + 1):
        if wh in by_hash:                        # this window matches some pattern's hash
            window = text[i:i + m]
            for p in by_hash[wh]:
                if window == p:
                    found[p].append(i)
        if i < n - m:
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return found
# endregion

"""The library counterpart and the contrast. For a single pattern you'd use Python's built-in
`str.find` (C, hybrid two-way) — that's the correctness reference. The instructive contrast for
Rabin-Karp's multi-pattern superpower is KMP from last chapter: to search for k patterns with a
single-pattern algorithm, you run it k times, sweeping the text once per pattern. Rabin-Karp
sweeps once for all k.

`kmp_search` below is last chapter's KMP, used both to cross-check correctness and to time the
"k separate searches" strategy against Rabin-Karp's single multi-pattern pass. (For genuinely
large pattern sets, the right tool is Aho-Corasick, a later chapter — Rabin-Karp multi-search is
the simplest way to see why one pass beats k.)
"""


# region: kmp
def _prefix(pattern):
    m = len(pattern)
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps


def kmp_search(text, pattern):
    """Last chapter's linear-time single-pattern search — the deterministic contrast to
    Rabin-Karp's hashing, and the per-pattern cost when searching a set the naive way."""
    if not pattern:
        return list(range(len(text) + 1))
    lps = _prefix(pattern)
    matches, j = [], 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]
    return matches
# endregion


# region: builtin
def find_all_builtin(text, pattern):
    """All occurrences via str.find — the trusted correctness reference."""
    if not pattern:
        return list(range(len(text) + 1))
    out, i = [], text.find(pattern)
    while i != -1:
        out.append(i)
        i = text.find(pattern, i + 1)
    return out
# endregion

Scratch vs library

Rabin-Karp and KMP solve the same single-pattern problem by opposite philosophies, and the contrast is the lesson. KMP is deterministic: it never errs, and it exploits the structure of the pattern. Rabin- Karp is probabilistic: it accepts a $10^{-18}$ chance of a collision (caught by verification anyway) in exchange for turning strings into numbers — and numbers can be hashed, set-membership-tested, and compared in O(1) regardless of length, which is what unlocks multi-pattern and multi-dimensional search. That's a general trade worth internalizing: randomization and hashing often buy you capabilities, not just speed — the ability to fingerprint, deduplicate, and batch-compare — that deterministic methods can't easily match. For a single pattern you'd use str.find; for many patterns you'd reach for Aho-Corasick or, for the simplest thing that works, exactly this. Building the rolling hash yourself is what makes rsync and content-defined chunking legible later — they're all this one O(1) update.

Where you'll actually meet it

The rolling hash is one of the most widely deployed ideas in systems software. rsync and cloud-backup deduplication use it to find matching blocks between files without transferring them, rolling a hash to detect shared content even when data shifts. Content-defined chunking (in backup, container registries, and Git's packing) uses rolling-hash boundaries to split files into stable chunks. Plagiarism detectors and near-duplicate search fingerprint documents with overlapping rolling hashes (the "winnowing" technique). Intrusion-detection and antivirus engines match many signatures at once with Rabin-Karp-style multi-pattern hashing. Bioinformatics uses it for k-mer indexing of DNA. And it's a staple of competitive programming for string equality and 2-D matching. Wherever you need to compare or fingerprint substrings cheaply and in bulk, a rolling hash is doing the work.

Takeaways

Rabin-Karp searches by hashing: a polynomial rolling hash turns each length-m text window into a number in O(1) per slide, numbers are compared instead of strings, and a character check verifies each hash match to catch the astronomically rare collision — O(n+m) expected. For one pattern it's a probabilistic alternative to KMP with no asymptotic edge, but its strengths are unique: searching many equal-length patterns in a single pass (200× faster than KMP-per-pattern at 800 patterns), two-dimensional matching, and — most valuably — the rolling hash itself, the fingerprinting primitive behind rsync, deduplication, and plagiarism detection.

The next chapter returns to deterministic single-pattern search but flips the direction of scanning. Boyer-Moore matches the pattern right to left and, on a mismatch, uses what it learns to jump forward by many characters at once — often skipping over large stretches of the text entirely, so that it examines fewer than n characters on average. Where KMP and Rabin-Karp both read every text character, Boyer-Moore reads a fraction of them, which is why it's the algorithm inside grep.