🎓 A1Learner
🔍
0 of 93 lessons completed

DSA Rabin–Karp Rolling Hash

The Rabin-Karp algorithm searches a text by comparing a rolling hash of each window against the pattern hash. A rolling hash is a number for a window that updates in one step when the window slides.

Two strings, one hash

The small modulus 101 keeps the arithmetic printable. It also makes collisions easy to meet, which the later checks rely on.

BASE = 31
MOD = 101


def hash_of(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch)) % MOD
    return value


print("Hash of aaa:", hash_of("aaa"))
print("Hash of cdf:", hash_of("cdf"))
print("Equal hashes, different strings:", hash_of("aaa") == hash_of("cdf"))

Rolling one step

Each new window hash comes from the previous one in a few arithmetic steps. The direct hashes beside them prove the rolling update is exact.

BASE = 31
MOD = 101


def hash_of(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch)) % MOD
    return value


def window_hashes(text, width):
    hashes = [hash_of(text[:width])]
    top = BASE ** (width - 1)
    for i in range(1, len(text) - width + 1):
        old = hashes[-1]
        rolled = (old - ord(text[i - 1]) * top) * BASE + ord(text[i + width - 1])
        hashes.append(rolled % MOD)
    return hashes


text = "abcde"
rolled = window_hashes(text, 3)
direct = [hash_of(text[i:i + 3]) for i in range(3)]
print("Rolled hashes:", rolled)
print("Direct hashes:", direct)
print("Rolling agrees:", rolled == direct)

A false hit, rejected

The window cdf hashes exactly like the pattern aaa. The letter-by-letter check runs and refuses the match.

BASE = 31
MOD = 101


def hash_of(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch)) % MOD
    return value


def search(text, pattern):
    target = hash_of(pattern)
    width = len(pattern)
    hash_hits = 0
    matches = []
    for i in range(len(text) - width + 1):
        if hash_of(text[i:i + width]) == target:
            hash_hits += 1
            if text[i:i + width] == pattern:
                matches.append(i)
    return matches, hash_hits


matches, hits = search("xxcdfyy", "aaa")
print("Hash hits:", hits)
print("Verified matches:", matches)

Example

BASE = 31
MOD = 101


def hash_of(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch)) % MOD
    return value


def search(text, pattern):
    target = hash_of(pattern)
    width = len(pattern)
    top = BASE ** (width - 1)
    current = hash_of(text[:width])
    windows = 0
    hash_hits = 0
    false_hits = 0
    matches = []
    for i in range(len(text) - width + 1):
        if i > 0:
            current = (current - ord(text[i - 1]) * top) * BASE
            current = (current + ord(text[i + width - 1])) % MOD
        windows += 1
        if current == target:
            hash_hits += 1
            if text[i:i + width] == pattern:
                matches.append(i)
            else:
                false_hits += 1
    return matches, windows, hash_hits, false_hits


text = "cdfaaabaaa"
pattern = "aaa"
matches, windows, hits, false_hits = search(text, pattern)
print("Pattern hash:", hash_of(pattern))
print("Windows checked:", windows)
print("Hash hits:", hits)
print("False hits rejected:", false_hits)
print("Matches:", matches)

Key points

  • Only windows whose hash equals the pattern hash are compared letter by letter
  • Sliding the window removes the leaving letter, shifts the rest, and adds the entering letter
  • A collision is a hash hit where the window text differs from the pattern, and the letter check rejects it
  • This lesson uses an arithmetic polynomial hash, because the built-in hash of a string changes between runs
  • Most windows are skipped by one hash comparison, so the search is fast on ordinary text

In this example, eight windows slide across the text and only three share the pattern hash. The first hit is the window cdf, a collision that the letter check rejects and counts. The other two hits verify as real matches at indices 3 and 7. Five windows were skipped after a single hash comparison each.

Note

The worst case is a text where every window collides, and then every window pays the full letter check

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A window hash equals the pattern hash, but the window text is not the pattern. What does Rabin-Karp do?