Rabin-Karp Rolling Hash Explained: O(1) Window Updates

The naive way to find a pattern in a text compares the pattern against every position, character by character. For a text of length n and a pattern of length m, that can cost n × m comparisons. Rabin-Karp replaces each window of text with a single number, a hash, and updates that number in constant time as the window slides. Comparing two numbers is cheap; the characters are only read again when the numbers agree.

The problem it solves

Find where a pattern occurs in a text. The brute-force check at each start position re-reads m characters that mostly overlap with the previous window: the window starting at 1 shares m - 1 characters with the window starting at 0. That repeated reading is the waste.

A rolling hash removes it. And because a window's identity becomes a number, the same idea answers questions that are awkward for character-by-character matching: "do these two documents share any 50-character passage?", "what is the longest substring that appears twice?". Those become lookups of numbers in a set.

The intuition

Treat a string as a number written in some base. With letters mapped to a = 0, b = 1, … and base 26, the window "abc" is 0·26² + 1·26 + 2 = 28. Real hashes use a larger base and reduce modulo a prime so the numbers stay small.

Sliding the window one place to the right is then arithmetic on that number, like shifting a decimal number one digit left:

1. Subtract the leaving character times base^(m-1), its place value.
2. Multiply by the base, which moves every remaining character up one place.
3. Add the arriving character in the units place.

Three operations, whatever the pattern length. The only price is that a hash taken modulo a prime squeezes many strings into few values, so two different strings can share a hash. A matching hash says "probably equal"; a character comparison confirms it. A mismatching hash is certain: equal strings always have equal hashes.

Watch it run

The animation uses the lesson's constants, base 26 and modulus 101, to search "abcabd" for "abd". The pattern hashes to 29. The window hashes are 28, 21, 40 and 29 as it slides, each one computed from the previous one rather than from scratch. Only the last window's hash equals the pattern's, and only there are the characters compared.

The code

A version that returns every match. It uses character codes with base 256 and a large prime modulus, so collisions are rare:

def rabin_karp(text, pat, base=256, mod=1_000_000_007):
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    high = pow(base, m - 1, mod)             # place value of the leaving char
    want = cur = 0
    for i in range(m):                       # hash the pattern and window 0
        want = (want * base + ord(pat[i])) % mod
        cur = (cur * base + ord(text[i])) % mod
    hits = []
    for i in range(n - m + 1):
        if cur == want and text[i:i + m] == pat:   # confirm: hashes can collide
            hits.append(i)
        if i + m < n:                        # roll one step to the right
            cur = (cur - ord(text[i]) * high) % mod
            cur = (cur * base + ord(text[i + m])) % mod
    return hits

print(rabin_karp("abcabd", "abd"))           # [3]
print(rabin_karp("abababa", "aba"))          # [0, 2, 4]
print(rabin_karp("abc", "abcd"))             # []

Why the character check matters. With the lesson's tiny modulus of 101, "afa" and "abd" hash to the same value, so a search that trusted the hash alone would report a match at 0:

def small_hash(s, base=26, mod=101):
    h = 0
    for c in s:
        h = (h * base + ord(c) - 97) % mod
    return h

print(small_hash("abd"), small_hash("afa"))  # 29 29
print(rabin_karp("afaabd", "abd", base=26, mod=101))   # [3]  (0 was rejected)

The rolling update and the full search, checked against Python's own slicing on 3,000 random texts over a small alphabet, where matches and overlaps are frequent. The check runs with the large modulus and with the small one, and counts the windows where the small hash matched but the characters did not, to show the rejection path really runs:

import random

def brute(text, pat):
    return [i for i in range(len(text) - len(pat) + 1) if text[i:i + len(pat)] == pat]

random.seed(26)
ok, spurious = True, 0
for _ in range(3000):
    text = "".join(random.choice("abcdef") for _ in range(random.randint(0, 40)))
    pat = "".join(random.choice("abcdef") for _ in range(random.randint(1, 4)))
    ok &= rabin_karp(text, pat) == brute(text, pat)
    ok &= rabin_karp(text, pat, base=26, mod=101) == brute(text, pat)
    m = len(pat)
    spurious += sum(small_hash(text[i:i + m]) == small_hash(pat) and text[i:i + m] != pat
                    for i in range(len(text) - m + 1))
print(ok, spurious > 0)                      # True True

The complexity

Hashing the pattern and the first window costs O(m). Each of the remaining n - m slides costs O(1). Each hash match then costs O(m) to verify.

• Expected time O(n + m), when matches are few and the modulus is large enough that spurious matches are rare.
• Worst case O(n × m), when many windows match. Searching "aaaa…a" for "aaa" makes every window a genuine match, and each is verified in full. An adversary who knows a fixed base and modulus can also construct collisions deliberately; choosing the base at random when the program starts takes that knowledge away.
• Space O(1) beyond the output list.

For a guaranteed O(n + m) single-pattern search, KMP is the standard answer. Rabin-Karp earns its place when you need to compare many windows as numbers: several patterns of the same length checked against one set of hashes, or substrings of two documents compared through a hash set.

Where it goes wrong

• Skipping the verification. Returning on a hash match alone is a bug that passes most tests and fails on the first collision, as the "afa" example shows.
• Negative intermediate values. In C, Java or JavaScript, cur - leaving * high can go negative, and % keeps the sign. Add mod before reducing. Python's % already returns a non-negative result.
• Overflow. In languages with fixed-width integers, cur * base can overflow before the modulus is applied. Keep mod small enough that the product fits, or use 64-bit arithmetic with care.
• Recomputing base^(m-1) every slide. It never changes. Compute it once, with modular exponentiation.

How to say it in an interview

"I treat each window of length m as a number in some base, modulo a large prime. Sliding by one is O(1): subtract the leaving character times base to the m minus 1, multiply by the base, add the arriving character. I compare window hashes with the pattern's hash, and only on a match do I compare characters, because different strings can collide. That's O(n + m) expected, O(n·m) in the worst case when many windows match or collide. If I need a guaranteed linear bound for one pattern I'd use KMP; Rabin-Karp is the better tool when I'm comparing many substrings as numbers."

For the fixed-width window mechanics without hashing, see the sliding window; for how hash functions and collisions behave in general, hash table basics.