Rabin-Karp in Python: Finding Substrings With Rolling Hashes

Substring search done the obvious way re-reads the pattern at every position in the text. Rabin-Karp does something stranger: it turns every window of the text into a single number and compares numbers instead of strings. Comparing two integers costs the same whether the pattern is 3 characters or 300.

That trade only pays off because of one arithmetic trick. Once you know the number for the window starting at position i, you can get the number for the window starting at i + 1 in constant time — subtract the leading character's contribution, shift, add the new trailing character. That is the rolling hash, and it is the entire algorithm.

Be clear about where it is genuinely useful, though. For finding one string inside another in Python, text.find(pattern) beats anything you write here, and KMP has the better worst case. Rabin-Karp earns its place elsewhere: hunting ten thousand patterns at once, or wanting a cheap hash of every window for its own sake — deduplication, backup chunking, plagiarism detection.

The idea

Give every string of length m a number, by reading it as a number written in base B — exactly as 407 is 4 × 10² + 0 × 10 + 7 in base 10. Map the characters to digits (a is 0, b is 1, up to z as 25) and take the base to be the alphabet size, 26. Then "ban" is 1 × 26² + 0 × 26 + 13 = 689.

That mapping is exact: distinct strings of the same length get distinct numbers, because base-26 digits are unique. But you cannot afford the numbers — a 40-character window in base 256 is a 320-bit integer, and arithmetic on it is no longer constant time. So take it modulo a prime P that fits in a machine word. The hash is now small and fast, and equal hashes only mean the strings are probably equal. That word "probably" separates a correct implementation from a broken one.

Here is the baseline you are trying to beat:

def naive_search(text: str, pattern: str) -> list[int]:
    """Return every start index where pattern occurs in text, by direct comparison."""
    n, m = len(text), len(pattern)
    matches: list[int] = []
    for start in range(n - m + 1):
        # This slice comparison can look at up to m characters.
        if text[start:start + m] == pattern:
            matches.append(start)
    return matches


print(naive_search("banana", "ana"))
print(naive_search("aaaaa", "aa"))

[1, 3]
[0, 1, 2, 3]

There are n - m + 1 starting positions and each comparison can cost up to m characters, so the worst case is O(n·m). On English text it behaves far better, because most comparisons die on the first character — but "usually fine" is not a bound, and the pathological input ("aaaa…a" searched for "aaa…ab") really does cost the full product.

Rabin-Karp replaces that inner comparison with an integer comparison:

The rolling update

Computing each of those hashes from scratch costs O(m), and there are n - m + 1 of them, so you are back at O(n·m) and have gained nothing. The win comes from how much consecutive windows share.

Window i covers text[i] through text[i + m - 1]; window i + 1 covers text[i + 1] through text[i + m]. They share m - 1 characters, so going from one to the next is three digit operations:

• Remove the leading digit. text[i] is the most significant digit of window i, contributing value(text[i]) · B^(m-1). Subtract exactly that.
• Shift left one place. Multiply by B, moving every remaining character up one power. That is what sliding means.
• Append the new digit. Add value(text[i + m]) in the now-empty units place.

As one line, everything taken modulo P:

hash(i + 1) = ((hash(i) - value(text[i]) * high_power) * B + value(text[i + m])) % P

where high_power is B^(m-1) % P, computed once before the loop. Three multiplications and an addition, none of them depending on m. That is the O(1) step that makes the whole thing worth doing.

Watching it work

Take the text "banana" and the pattern "ana", with base 26 and modulus 101. The letter values are a = 0, b = 1, n = 13.

The pattern first: "ana" is 0 × 676 + 13 × 26 + 0 = 338, and 338 mod 101 = 35. That number is computed once and never again. The first window, "ban", is 1 × 676 + 0 × 26 + 13 = 689, and 689 mod 101 = 83. Not 35, so no match at position 0. Every window after that comes from the rolling update, with high_power = 26² mod 101 = 676 mod 101 = 70.

Roll from "ban" to "ana". The character leaving is b, worth 1, so subtract 1 × 70 = 70: 83 - 70 = 13. Shift: 13 × 26 = 338. The character entering is a, worth 0, so add nothing. 338 mod 101 = 35, which equals the pattern hash — so verify the characters, text[1:4] really is "ana", and report a match at index 1.

Roll from "ana" to "nan". Leaving is a, worth 0, so subtract nothing: still 35. Shift: 35 × 26 = 910. Entering is n, worth 13: 910 + 13 = 923, and 923 mod 101 = 14 since 101 × 9 = 909. Not 35, no match.

Roll from "nan" to "ana". Leaving is n, worth 13: 14 - 13 × 70 = 14 - 910 = -896. This is where hand-written implementations break, because the intermediate went negative. Python's % always returns a non-negative result for a positive modulus, so -896 % 101 is 13 and the arithmetic carries on. Shift and append: 13 × 26 = 338, plus 0, mod 101 = 35. Another hit, verified, match at index 3.

Here are those hashes computed the slow way, one full pass per window:

BASE = 26
MOD = 101


def letter_value(character: str) -> int:
    """Map 'a'..'z' onto the digits 0..25 of a base-26 number."""
    return ord(character) - ord("a")


def slow_window_hash(window: str) -> int:
    """Read a string as a base-26 number, kept small by a modulus. Costs O(len(window))."""
    value = 0
    for character in window:
        value = (value * BASE + letter_value(character)) % MOD
    return value


text, pattern = "banana", "ana"
m = len(pattern)

print("pattern", pattern, "->", slow_window_hash(pattern))
for start in range(len(text) - m + 1):
    print(start, text[start:start + m], "->", slow_window_hash(text[start:start + m]))

pattern ana -> 35
0 ban -> 83
1 ana -> 35
2 nan -> 14
3 ana -> 35

And here is the same sequence of numbers produced by rolling, with only one multiplication and one addition per window:

high_power = pow(BASE, m - 1, MOD)  # 26 ** 2 mod 101: the weight of the leading character
rolling = slow_window_hash(text[:m])

print("high_power", high_power)
print(text[:m], rolling)
for start in range(len(text) - m):
    leaving = letter_value(text[start])
    entering = letter_value(text[start + m])
    rolling = ((rolling - leaving * high_power) * BASE + entering) % MOD
    print(text[start + 1:start + 1 + m], rolling)

high_power 70
ban 83
ana 35
nan 14
ana 35

Identical hashes, one constant-time step each. Note pow(BASE, m - 1, MOD): Python's three-argument pow does modular exponentiation in O(log m) multiplications rather than m of them, the technique in fast exponentiation.

Spurious hits

Now break it deliberately. Keep base 26 but drop the modulus to 31, still prime but far too small. "ana" is 338 and 338 mod 31 = 28; "nan" is 13 × 676 + 0 + 13 = 8801 and 8801 mod 31 = 28 as well. Two windows sharing no arrangement of characters now hash identically.

That is a spurious hit: equal hashes, unequal strings. You cannot eliminate it, because you are mapping every possible m-character string into P buckets and there are vastly more strings than buckets. The only defence is the one the algorithm builds in: when the hashes match, compare the actual characters before reporting anything. Skip that check to save time and you have written a search that returns wrong answers on inputs you will never think to test.

A large prime does not remove collisions, it makes them rare — which is the whole point of the modulus choice:

• Prime matters. A modulus sharing factors with the base throws information away. The extreme case is a power of the base, B = 256 with P = 2^24: that keeps only the window's last three bytes and discards every earlier character, so "...abc" and "...xyz abc" collide by construction. A prime shares no factors with a sensible base, so all P residues stay reachable.
• Large matters. For a hash spread evenly over P values, two different windows collide with probability about 1/P. With P near 10^9, scanning a million-character text you expect roughly 10^6 / 10^9 = 0.001 spurious hits. With P = 31 you expect one every 31 windows.
• The base should be at least the alphabet size, so distinct characters are distinct digits, and coprime to the modulus. 256 for bytes; 31 and 257 are common for text.

The code

The real implementation, with a byte-sized base and a prime near a billion:

def rabin_karp_search(text: str, pattern: str, base: int = 256,
                      modulus: int = 1_000_000_007) -> list[int]:
    """Return every start index where pattern occurs in text.

    Each window's hash is derived from the previous window's in constant time,
    and every hash match is verified against the real characters before it is
    reported, because two different windows can share a hash.
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []

    high_power = pow(base, m - 1, modulus)
    pattern_hash = 0
    window = 0
    for index in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[index])) % modulus
        window = (window * base + ord(text[index])) % modulus

    matches: list[int] = []
    for start in range(n - m + 1):
        # The slice runs only when the hashes agree, so it is rare on real text.
        if window == pattern_hash and text[start:start + m] == pattern:
            matches.append(start)
        if start < n - m:
            leaving = ord(text[start])
            entering = ord(text[start + m])
            window = ((window - leaving * high_power) * base + entering) % modulus

    return matches


print(rabin_karp_search("banana", "ana"))
print(rabin_karp_search("abracadabra", "abra"))
print(rabin_karp_search("aaaa", "aa"))
print(rabin_karp_search("hello", "world"))
print(rabin_karp_search("hi", "longer pattern"))

[1, 3]
[0, 7]
[0, 1, 2]
[]
[]

How the code maps to the idea

The setup loop builds both hashes at once, walking the pattern and the first window together with Horner's method: multiply the running value by the base, add the next digit, reduce. That loop is the O(m) preprocessing cost, and the only place a hash is built from scratch.

high_power is B^(m-1) mod P — the weight of the leading character. It never changes, so it is computed once. Getting it wrong by one power (using B^m) is the most common bug here, and the symptom is that everything silently stops matching.

ord(character) is the digit mapping. Base 256 with ord handles ASCII directly. Non-ASCII survives too — ord goes well past 255, so digits can exceed the base, but the hash stays a deterministic function of the characters. For byte-level work, encode to UTF-8 first and hash the bytes.

The verification is the and in the condition. Python short-circuits, so the slice comparison only runs when the hashes already agree. On text with few matches it almost never executes, which is exactly why the average case is linear.

The guarded roll. The update sits behind if start < n - m because the last window has no text[start + m] to read. Without the guard, every search ends in an IndexError.

Edge cases. An empty pattern returns every position from 0 to n, matching the convention that an empty string occurs everywhere; it needs a special case because high_power is meaningless for m = 0. A pattern longer than the text returns before any arithmetic. Overlapping matches fall out free — the window advances one character, not m, which is why "aaaa" searched for "aa" reports 0, 1 and 2.

Spurious hits are measurable. This counts how often the hashes agree against how often the strings really match, on a 1,200-character text built by repeating "banana":

def count_hash_hits(text: str, pattern: str, modulus: int) -> tuple[int, int]:
    """Return (hash hits, verified matches) for the base-26 lowercase hash."""
    m = len(pattern)
    high_power = pow(BASE, m - 1, modulus)
    pattern_hash = window = 0
    for index in range(m):
        pattern_hash = (pattern_hash * BASE + letter_value(pattern[index])) % modulus
        window = (window * BASE + letter_value(text[index])) % modulus

    hits = verified = 0
    for start in range(len(text) - m + 1):
        if window == pattern_hash:
            hits += 1
            if text[start:start + m] == pattern:
                verified += 1
        if start < len(text) - m:
            window = ((window - letter_value(text[start]) * high_power) * BASE
                      + letter_value(text[start + m])) % modulus
    return hits, verified


haystack = "banana" * 200  # 1,200 characters holding 400 real occurrences of "ana"
for modulus in (31, 101, 1_000_000_007):
    hits, verified = count_hash_hits(haystack, "ana", modulus)
    print(f"modulus {modulus:>10}: {hits} hash hits, {verified} verified matches")

modulus         31: 600 hash hits, 400 verified matches
modulus        101: 400 hash hits, 400 verified matches
modulus 1000000007: 400 hash hits, 400 verified matches

Modulus 31 produces 200 wasted character comparisons — one for every "nan" in the text. Modulus 101 already separates those two windows. The billion-sized prime is what you would actually ship.

Complexity

Preprocessing: O(m). One pass over the pattern and one over the first window, plus pow(base, m - 1, modulus), which is O(log m) multiplications.

The scan: O(n) hash work. There are n - m + 1 windows, and each rolling update is a fixed three multiplications, one subtraction, one addition and one modulo. No part of it depends on m.

Verification: O(m) per hash hit. Two kinds of hit exist. Real matches: if the pattern occurs k times you compare k · m characters, which no algorithm reporting every occurrence can avoid. Spurious hits: with the hash spread evenly over P residues each window collides with probability about 1/P, so the expected count is n / P and the expected wasted work is n · m / P characters. On a million-character text with a 100-character pattern and P = 10^9, that is 10^6 × 100 / 10^9 — a tenth of one character comparison.

Average case: O(n + m). Add the three: O(m) preprocessing, O(n) rolling, O(k · m + n · m / P) verification. With few occurrences and a large prime the last term rounds away, leaving a bound linear in the total input size.

Worst case: O(n·m). This happens whenever every window produces a hit. The easy trigger is a text and pattern of one repeated character, where every window is a genuine match and each verification honestly costs m:

worst_text = "a" * 2000
worst_pattern = "a" * 100
found = rabin_karp_search(worst_text, worst_pattern)
print(len(found), "windows matched;", len(found) * len(worst_pattern), "characters compared")

1901 windows matched; 190100 characters compared

The dangerous trigger is adversarial. Base and modulus are usually constants in the source, so anyone who can read the code can build a text whose every window collides with the pattern hash, turning a linear search quadratic on demand. If the input comes from strangers, pick the modulus or base randomly at process start.

Space: O(1). A handful of integers, however long the text is. The multi-pattern version below needs O(k) for a dictionary of k pattern hashes.

One caveat about "constant time" arithmetic: it holds while the numbers fit in a machine word. Keep the modulus below 2^31 if intermediate products must fit in a signed 64-bit integer, since (window - leaving * high_power) * base can reach roughly P × B. Python integers are arbitrary precision so nothing overflows, but arithmetic on numbers far larger than a word stops being constant time.

Searching for many patterns at once

This is where Rabin-Karp stops being an academic exercise. A window's hash does not know what it is being compared against, so instead of comparing it to one number, look it up in a dictionary of many.

Put every pattern's hash in a dict keyed by hash and run the same single pass, checking each window's hash against the dict. That lookup is O(1) whether you are searching for 4 patterns or 40,000. KMP cannot do this — its skip table is built from one specific pattern, so k patterns means k passes.

def rabin_karp_multi(text: str, patterns: list[str], base: int = 256,
                     modulus: int = 1_000_000_007) -> list[tuple[int, str]]:
    """Find every occurrence of any of the patterns, which must share one length.

    The rolling hash is unchanged; only the comparison changes, from one number
    to a dictionary lookup. That lookup costs the same whether there is one
    pattern or a hundred thousand.
    """
    if not patterns:
        return []
    m = len(patterns[0])
    if any(len(item) != m for item in patterns):
        raise ValueError("every pattern must have the same length")

    n = len(text)
    if m == 0 or m > n:
        return []

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

    high_power = pow(base, m - 1, modulus)
    window = 0
    for index in range(m):
        window = (window * base + ord(text[index])) % modulus

    found: list[tuple[int, str]] = []
    for start in range(n - m + 1):
        # Two different patterns can collide too, so still verify each candidate.
        for candidate in by_hash.get(window, ()):
            if text[start:start + m] == candidate:
                found.append((start, candidate))
        if start < n - m:
            window = ((window - ord(text[start]) * high_power) * base
                      + ord(text[start + m])) % modulus

    return found


sentence = "the quick brown fox jumps over the lazy dog"
print(rabin_karp_multi(sentence, ["quick", "brown", "jumps", "zebra"]))

needles = [f"id{index:03d}" for index in range(1000)]  # 1,000 patterns, all length 5
log_line = "user id042 opened id777 and closed id042 again"
print(rabin_karp_multi(log_line, needles))

[(4, 'quick'), (10, 'brown'), (20, 'jumps')]
[(5, 'id042'), (18, 'id777'), (35, 'id042')]

The second search checks a thousand patterns against 45 characters in one pass, at the same cost as searching for one. The dict values are lists rather than single strings because two patterns can collide with each other, which needs the same verification treatment.

The restriction is real, though: every pattern must be the same length, because one rolling hash tracks one window size. Patterns of d distinct lengths need d passes. If d is large, use Aho-Corasick instead — it handles mixed lengths in one pass with an automaton built from a trie.

When to use it, and when not to

Use it for many patterns of one length. Blocklists of fixed-length tokens, a set of known hashes, a dictionary of 5-grams: one pass, one dict lookup per position.

Use it when the rolling hash is the product, not the search. Content-defined chunking, fingerprinting every substring of a document, finding duplicate blocks between two files — these want a hash of every window and never do exact matching at all. The rolling update is the only reason they are affordable.

Use it when you want a short, obviously-correct implementation. It is about 20 lines you can re-derive from the base-B idea. KMP's failure function is easier to get subtly wrong.

Do not use it for a single pattern in Python. The built-ins are written in C and are strictly better:

import re

print("banana".find("ana"))
print([match.start() for match in re.finditer("(?=ana)", "banana")])

1
[1, 3]

str.find and the in operator use CPython's fastsearch: a Boyer-Moore-Horspool variant with a bitmask skip table, plus the two-way algorithm for long needles since Python 3.10 to avoid quadratic blowups. The lookahead in re.finditer("(?=ana)", …) is how you get overlapping matches, which a find loop misses unless it advances by one character rather than by the pattern length.

Do not use it when the worst case must be bounded. Rabin-Karp is O(n·m) in the worst case, and an attacker can construct that case. KMP is O(n + m) always, with no probabilistic argument anywhere in it.

Do not use it for approximate matching. A rolling hash tells you two windows are equal, never how similar they are — change one character and the hash is unrelated. For "how different are these two strings", reach for edit distance.

Where it shows up in the real world

rsync is the clearest example of the shape, even though it does not use a polynomial hash. To work out which blocks of a file the far end already has, it rolls a weak checksum (a variant of Adler-32) over every byte offset, looks each value up in a hash table of the remote block checksums, and only then confirms a hit with a strong hash — MD4 originally, MD5 in current versions. Cheap rolling hash, expensive verification.

Content-defined chunking is Rabin's fingerprint doing what it was designed for. The Low-Bandwidth Network File System (LBFS, 2001) introduced it: roll a hash over a small sliding window and cut a chunk boundary wherever the hash's low bits are all zero. Because boundaries depend on content rather than offset, inserting a byte at the front of a file shifts only the chunk containing it — every other chunk keeps its identity and does not need re-uploading. restic does exactly this with a Rabin fingerprint in its chunker package; borgbackup does the same job with a different rolling hash (buzhash), which tells you the structure matters more than the specific function.

Plagiarism and near-duplicate detection. The winnowing algorithm behind MOSS (Schleimer, Wilkerson and Aiken, 2003) hashes every k-gram of a document and keeps a sample as its fingerprint; Karp-Rabin hashing is what makes hashing every k-gram affordable. Broder's shingling work on near-duplicate web pages at AltaVista used Rabin fingerprints of overlapping word sequences for the same reason.

Interview and contest problems. Rolling hashes solve a family of questions that look unrelated to string search: counting distinct substrings of a given length, finding the longest substring common to two strings by binary searching the length, and comparing two long substrings in O(1) after O(n) preprocessing.

Common mistakes

Not verifying the characters. The serious one. Equal hashes are evidence, not proof. An implementation that reports a match on hash equality alone is wrong, and wrong rarely enough that testing will not find it.

Recomputing each window hash from scratch. If the inner loop walks m characters you have written the naive algorithm with extra arithmetic. The update must be O(1).

Using B^m instead of B^(m-1). The leading character sits in place m - 1. This produces a search that finds nothing, which at least fails loudly.

Letting the intermediate go negative in a language without floor modulo. window - leaving * high_power is often negative. Python's % returns a non-negative result, so this just works; in C, C++, Java, Go or Rust it does not, and the search silently misses matches unless you add modulus back.

A modulus that is too small, or shares factors with the base. Modulus 31 gave a spurious hit every few windows above, and a power-of-two modulus with base 256 is worse than small — it discards everything but the last few characters.

Reaching for Python's built-in hash(). It cannot roll, and it is randomised per process by default, so results are not reproducible across runs.

Forgetting overlapping matches. After a match at index i the next window starts at i + 1, not i + m. Skipping ahead by the pattern length misses the second "ana" in "banana".

Practice

1. Add an early return to rabin_karp_search so it stops at the first match and returns -1 when there is none, mirroring str.find.
2. Count the distinct substrings of length k in a string by rolling one hash across it and collecting the values in a set, then explain why the answer can be slightly too low.
3. Extend rabin_karp_multi to accept patterns of different lengths by grouping them by length and running one pass per group, and count how many passes a realistic blocklist needs.
4. Implement double hashing: carry two rolling hashes with different primes and treat a hit as a hit only when both agree. Measure how many spurious hits survive on the "banana" * 200 text with moduli 31 and 37.
5. Write a content-defined chunker: roll a hash over a 48-byte window and cut a boundary wherever hash % 4096 == 0. Insert a character at the front of the input and show that all chunks after the first are unchanged.

Summary

Rabin-Karp is a good algorithm attached to a great primitive. The search itself is rarely the right tool for one pattern in one text — the standard library is faster and KMP has a stronger guarantee. The rolling hash underneath it is what matters: constant-time hashing of every window is the foundation of backup deduplication, rsync's block matching, and every plagiarism detector that fingerprints k-grams. Learn the update arithmetic, and remember that a hash match is a hint that must always be checked.

Keep reading

• The KMP Algorithm — the other classic string search, with a guaranteed linear worst case and no hashing at all.
• Hash Tables — where hash functions, collisions and buckets are explained from first principles.
• Fast Exponentiation — how pow(base, m - 1, modulus) computes a huge modular power in O(log m) steps.
• Big O Notation — the counting arguments used to justify O(n + m) above.