Rabin-Karp Algorithm

#How does it work?

Instead of comparing letters one by one, Rabin-Karp compares numbers: it computes a hash of the pattern and compares it with the hash of every m-letter window of the text.

The trick is the rolling hash: when the window moves one step right, its hash isn't recomputed from scratch; the contribution of the letter leaving on the left is removed and the one entering on the right is added. That makes each step O(1).

Different strings can share a hash (a collision). So when the hashes are equal the letters are still checked; equal hashes with different letters are a spurious hit. In the example, FUN and DOG share a hash.

#Try it yourself

#Step by step

1. 01Compute the hash of the pattern and of the text's first m letters.
2. 02If the hashes differ, move on without looking at the letters.
3. 03If they are equal, compare the letters: a match if they agree, a spurious hit if not.
4. 04Slide the window and update the hash in constant time (rolling hash).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

BASE, MOD = 26, 101  # a small modulus so collisions show up; real code uses a large prime


def code(c: str) -> int:
    return ord(c) - ord("A") + 1  # A = 1 .. Z = 26


def rabin_karp(text: str, pattern: str):
    """Returns (match positions, number of spurious hits)."""
    n, m = len(text), len(pattern)
    high = pow(BASE, m - 1, MOD)  # weight of the leftmost letter
    p = t = 0
    for k in range(m):
        p = (p * BASE + code(pattern[k])) % MOD
        t = (t * BASE + code(text[k])) % MOD
    found, spurious = [], 0
    for s in range(n - m + 1):
        if t == p:  # equal hashes: the letters still have to be checked
            if text[s:s + m] == pattern:
                found.append(s)
            else:
                spurious += 1
        if s + m < n:  # roll: drop text[s], add text[s + m]
            t = ((t - code(text[s]) * high) * BASE + code(text[s + m])) % MOD
    return found, spurious


found, spurious = rabin_karp("FUNNYDOGFUN", "DOG")
print(" ".join(map(str, found)))
print(spurious)  # FUN has the same hash as DOG

#Complexity

With a good base and a large prime modulus, collisions are very rare and the algorithm is linear in practice. The lesson deliberately uses a small modulus (101) so the numbers stay readable; real implementations use large primes such as 10⁹ + 7 or two different hashes.

#When to use it?

Searching for many patterns at once (keep all pattern hashes in a set), plagiarism detection, finding repeated chunks in files (rsync, data deduplication) and two-dimensional pattern search all build on the Rabin-Karp idea.

#Practice

Log in to answer questions and save your progress.