Rabin-Karp Algorithm

Rabin-Karp searches for a pattern by comparing rolling hashes of text windows, enabling efficient multi-pattern search.

Compare hashes, not characters

Rabin-Karp finds a pattern in text by hashing the pattern once and comparing it against the hash of each window of the text of the same length. Two strings that differ must, with a good hash, almost always have different hashes, so most windows are rejected by a single integer comparison rather than a character-by-character check.

The rolling hash

Recomputing each window's hash from scratch would be O(m) per position and defeat the purpose. A rolling hash updates the hash in O(1) when the window slides by one: it removes the contribution of the departing character and adds the incoming one. Treating the string as a number in some base modulo a large prime makes this arithmetic exact and fast.

python

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

• Average and best case: O(n + m)
• Worst case: O(n*m) if many hash collisions occur
• Verify on hash match to rule out false positives
• Naturally extends to searching many patterns at once

Collisions and verification

A hash match is not proof of a real match: two different windows can share a hash, a spurious hit. Rabin-Karp confirms every hash match with a direct character comparison. With a good hash and a large modulus, collisions are rare, so the amortized cost stays linear, but an adversarial text can force the O(n*m) worst case.

Its niche

Rabin-Karp shines when searching for many patterns at once, since all their hashes can be checked against each window, and in plagiarism detection where document fingerprints are compared. For a single pattern with a guaranteed linear worst case, KMP is the safer choice.