---
title: Rabin–Karp
source: 'https://academia.sh/en/courses/algorithms/rabin-karp'
course: Algorithms
language: en
updated: '2026-08-17T18:07:48+00:00'
license: 'CC BY-SA 4.0'
---

# Rabin–Karp

Pattern matching with a rolling hash, constant-cost window updates, collision verification, worst case, and its advantage in multi-pattern search.

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

```python
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.

```python
# 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.

```python
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.