Rabin–Karp

Brute-force search compared characters one by one in every window. This lesson’s idea turns comparison into a completely different operation: reduce every window of the text to a number and compare numbers.

Comparing numbers is a single operation. The problem is that computing each window’s number takes $O(m)$ — as it stands, there is no gain at all. The solution is to not compute the number from scratch.

Rolling Hash

When a window shifts one character to the right, if the new hash value can be obtained from the old one with a constant number of operations, the method is called a rolling hash.

The hash used treats characters as digits of a number base. For base $b$ and prime modulus $q$, the value of a window of length $m$ is:

$$H = \left(\sum_{i=0}^{m-1} s_i \cdot b^{\,m-1-i}\right) \bmod q$$

When the window shifts right, the contribution of the leftmost character is subtracted, the remainder is shifted one digit, and the new character is added:

$$H' = \big((H - s_{\text{left}} \cdot b^{\,m-1})\cdot b + s_{\text{new}}\big) \bmod q$$

Three operations, independent of length: the update is $O(1)$.

Implementation

def rabin_karp(text: str, pattern: str,
                base: int = 256, modulus: int = 1_000_003) -> tuple[list[int], int, int]:
    """(positions, hash-match count, characters verified)"""
    n, m = len(text), len(pattern)
    if m > n:
        return [], 0, 0

    power = pow(base, m - 1, modulus)          # b^(m-1) mod q
    hash_pattern = hash_text = 0
    for i in range(m):                          # first window and the pattern
        hash_pattern = (hash_pattern * base + ord(pattern[i])) % modulus
        hash_text = (hash_text * base + ord(text[i])) % modulus

    positions: list[int] = []
    matches, verifications = 0, 0
    for shift in range(n - m + 1):
        if hash_text == hash_pattern:           # candidate: hashes equal
            matches += 1
            verifications += m
            if text[shift:shift + m] == pattern:
                positions.append(shift)
        if shift < n - m:                       # roll the window
            hash_text = (hash_text - ord(text[shift]) * power) % modulus
            hash_text = (hash_text * base + ord(text[shift + m])) % modulus
    return positions, matches, verifications


text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(rabin_karp(text, pattern))          # ([10], 1, 9)
print(rabin_karp("ABABAB", "AB"))         # ([0, 2, 4], 3, 6)

Of the text’s eleven windows, only one passes the hash test, and nine characters are read for verification. The difference is clear against the 29 comparisons brute force made on the same input.

Because Python’s remainder operation produces a non-negative result on negative numbers, intermediate values need no correction; in languages that use fixed-width integers, a modulus correction is added after the subtraction. The signed-arithmetic difference from the How Computers Work course can turn into a concrete bug here.

Collision and Verification

Hash equality does not prove that two sequences are equal. Different sequences can fall on the same value — the same collision concept from the Data Structures course.

For this reason, every hash match is verified by character comparison. Without verification, the algorithm produces a wrong result.

# If the modulus is deliberately chosen small, collisions increase
print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB", modulus=7))
# ([10], 4, 36)

With a small modulus, four windows pass the hash test, but only one is a real match; the other three are eliminated during verification. The result is still correct — the cost is the wasted character comparisons.

This is the general pattern of hash-based methods: the hash filters, verification decides.

Cost

Expected cost is $O(n + m)$: each window takes constant work, and the collision probability is negligible once the modulus is chosen large enough.

The worst case is $O(nm)$ and arises in two ways. The first is that there genuinely are a large number of matches (searching for "AA" inside "AAAA…") — this is unavoidable, because the output itself is large. The second is text constructed to produce collisions against the chosen hash function; choosing the modulus at random turns this attack into a mere probability.

Criterion	Brute force	Rabin–Karp
Preprocessing	None	$O(m)$
Expected search	$O(nm)$ worst case	$O(n + m)$
Worst-case search	$O(nm)$	$O(nm)$
Extra space	$O(1)$	$O(1)$

Choosing the Base and the Modulus

Two parameters determine the method’s behavior.

The base should not be smaller than the alphabet size; if it is, distinct character sequences regularly fall on the same value. For byte sequences, 256 works; for small alphabets, a value equal to the alphabet size is enough.

The modulus is chosen prime. A non-prime modulus that shares factors with the base piles hash values onto particular residues and increases collisions.

The size of the modulus is a question of overflow: the intermediate product hash * base must not exceed the language’s integer width. In sixty-four-bit arithmetic, keeping the modulus under roughly $2^{31}$ guarantees this. Python’s unbounded integers remove this constraint, at the cost of higher operation cost for large values.

The collision probability for a random modulus is approximately $m/q$ per window. If a stronger guarantee is needed, two independent hashes are used together; the probability of both colliding shrinks to the product of the two, and verification does almost no wasted work.

The Real Advantage: Multiple Patterns

The method’s clearest gain shows up not in single-pattern search but in searching for many patterns of the same length together. The patterns’ hash values are kept in a set; the text is scanned in a single pass, with one set lookup per window.

def multi_rabin_karp(text: str, patterns: list[str],
                      base: int = 256, modulus: int = 1_000_003) -> dict[str, list[int]]:
    m = len(patterns[0])
    if any(len(p) != m for p in patterns):
        raise ValueError("all patterns must have the same length")

    targets: dict[int, list[str]] = {}
    for p in patterns:
        h = 0
        for character in p:
            h = (h * base + ord(character)) % modulus
        targets.setdefault(h, []).append(p)

    power = pow(base, m - 1, modulus)
    h = 0
    for i in range(m):
        h = (h * base + ord(text[i])) % modulus

    result: dict[str, list[int]] = {p: [] for p in patterns}
    for shift in range(len(text) - m + 1):
        for candidate in targets.get(h, []):
            if text[shift:shift + m] == candidate:
                result[candidate].append(shift)
        if shift < len(text) - m:
            h = (h - ord(text[shift]) * power) % modulus
            h = (h * base + ord(text[shift + m])) % modulus
    return result


print(multi_rabin_karp("ABABDABACDABABCABAB", ["ABAB", "BACD", "CABA"]))
# {'ABAB': [0, 10, 15], 'BACD': [6], 'CABA': [14]}

Three patterns are found in a single pass over the text. For $k$ patterns, the cost is $O(n + km)$; searching for each pattern separately with brute force would be $O(knm)$.

The same idea extends to two dimensions: rolling row hashes make it possible to search for a rectangular pattern inside an image. The rolling hash is also used in areas such as content-defined chunking — the same constant-cost window update, put to a different purpose.

Summary

• Rabin–Karp reduces windows to a hash value and turns comparison into number equality.
• The rolling hash updates its value with a constant number of operations as the window shifts.
• Hash equality is not proof; every candidate is verified by character comparison.
• Expected cost is $O(n + m)$, worst case $O(nm)$; a random modulus protects against constructed inputs.
• The real advantage is searching for many patterns of the same length in a single pass: $O(n + km)$.

Next Step

Rabin–Karp compressed the pattern’s content into a number but never used its structure. Yet the overlap between the prefix and suffix of the pattern ABABCABAB tells us, at the moment of a mismatch, how many positions can safely be skipped. The next lesson computes this structure as a prefix function and builds a search that never backtracks in the text.