Rabin-Karp Algorithm

A hashing-based string search that slides a rolling hash to find pattern occurrences, extending naturally to multiple patterns.

Hashing a window

Rabin-Karp searches for a pattern of length m in a text by comparing hash values rather than characters. It computes the hash of the pattern and of each length-m window of the text; only when hashes match does it verify character by character. The trick is a rolling hash that updates in O(1) as the window slides.

The rolling hash

Kronos motion — classical

Treating the window as a base-B number modulo a large prime, sliding one position means subtracting the leaving character's contribution, multiplying by B, and adding the entering character. This gives O(n + m) expected time. A poor modulus can cause many spurious matches; a random large prime and double hashing keep collisions rare.

Update rule

python

def rabin_karp(text, pat, B=256, MOD=1_000_000_007):
    n, m = len(text), len(pat)
    if m > n: return []
    hp = ht = 0
    high = pow(B, m-1, MOD)
    for i in range(m):
        hp = (hp*B + ord(pat[i])) % MOD
        ht = (ht*B + ord(text[i])) % MOD
    res = []
    for i in range(n - m + 1):
        if hp == ht and text[i:i+m] == pat:
            res.append(i)
        if i < n - m:
            ht = ((ht - ord(text[i])*high)*B + ord(text[i+m])) % MOD
    return res

Strengths and weaknesses

Excels at multi-pattern search: hash all patterns of the same length into a set and test each window once.
Expected linear, but adversarial inputs can force O(n*m) if the hash is weak or fixed.
KMP and Z-algorithm give worst-case linear time without hashing.
Rolling hashes also power the Karp-Rabin 2D pattern match and content-defined chunking.

Modular arithmetic

The rolling hash is exactly modular arithmetic on a polynomial value; precomputing B^(m-1) mod p with fast exponentiation keeps the update constant time.