Rabin-Karp and Rolling Hashes

Comparing two strings of length $m$ character by character costs $O(m)$, which is fine once but expensive if you need to do it at every one of $n$ sliding positions across a text. Rabin-Karp sidesteps most of that work by comparing single numbers — hashes — instead of full strings, and only falls back to a real character comparison when two hashes happen to collide. The trick that makes this fast rather than merely clever is the rolling hash: updating the hash of a sliding window in $O(1)$ per step instead of recomputing it from scratch.

The idea: treat a string as a number in some base

Treat the window of $m$ characters as a number in base $b$ (say, 256 for byte values), reduced modulo a large prime $p$ to keep the number small:

$$h = \Big(\sum_{k=0}^{m-1} \text{char}_k \cdot b^{m-1-k}\Big) \bmod p$$

The rolling update, sliding the window one character to the right — dropping the leftmost character and appending a new one — is:

$$h_{\text{new}} = \big((h_{\text{old}} - \text{char}_{\text{leftmost}} \cdot b^{m-1}) \cdot b + \text{char}_{\text{new}}\big) \bmod p$$

In words: undo the leftmost character's contribution (it was weighted by $b^{m-1}$, the highest place value), shift everything up one place value by multiplying by $b$, then add the new character in the lowest place. This costs a fixed handful of arithmetic operations regardless of $m$, versus $O(m)$ to hash the window from scratch. Searching a text of length $n$ for a pattern of length $m$ is then $O(n + m)$ on average: $O(m)$ to hash the pattern once, then $O(1)$ per position to roll the text's window hash and compare against it, with an $O(m)$ verification step only on the rare hash collision.

Worked example: small numeric trace

Base $b=10$, modulus $p=101$ (toy values for hand-tracing). Digits 1,2,3,4,5, window size 3. hash("123") = (1·100 + 2·10 + 3) mod 101 = 123 mod 101 = 22. Roll to "234": subtract the leftmost digit's contribution $1 \cdot 10^{2} = 100$, giving $22 - 100 = -78$; multiply by base 10: $-780$; add new digit 4: $-776$; reduce mod 101 (adding multiples of 101 until non-negative): $-776 + 8\cdot101 = -776+808=32$. Check directly: hash("234") = (2·100+3·10+4) mod 101 = 234 mod 101 = 32. Matches — the rolling update reached the same answer as hashing from scratch, without re-reading digits 2 and 3.

def rabin_karp(text, pattern, base=256, mod=10**9+7):   # O(n+m) average
    n, m = len(text), len(pattern)
    if m > n:
        return []
    high_pow = pow(base, m - 1, mod)
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    matches = []
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i+m] == pattern:   # verify on collision
            matches.append(i)
        if i < n - m:
            t_hash = ((t_hash - ord(text[i]) * high_pow) * base + ord(text[i+m])) % mod
    return matches

Where it shows up

Interview framing: repeated DNA sequences, and Rabin-Karp is the standard approach for multi-pattern search (hash several patterns at once and check each window's hash against a set) where KMP's single-pattern machinery doesn't generalize as cleanly. On a desk, rolling hashes underlie fast duplicate or near-duplicate detection across large text or log corpora, and plagiarism-style similarity checks across strategy code or documentation, where hashing overlapping windows is far cheaper than pairwise full-string comparison.