Rabin-Karp, in depth: the rolling hash, overflow-safe arithmetic, collision bounds, multi-pattern search and substring hashing

The polynomial and the roll

Map each character to a number, for example its code point or a letter index. A string s of length m then becomes the polynomial H(s) = s[0]*b^(m-1) + s[1]*b^(m-2) + ... + s[m-1]*b^0, evaluated modulo a prime p. The base b plays the role of a radix: if b were larger than the alphabet and no modulus were taken, H would be an exact positional encoding, like reading the string as a number in base b. The modulus is what makes the number fit in a machine word, and it is also what makes collisions possible.

Compute the hash of the first window with Horner's rule, which avoids explicit powers: start with h = 0 and for each character set h = (h*b + value) mod p. Now look at what happens when the window moves from position i to i+1. The old window contributes t[i]*b^(m-1) at its high end. Subtract that, multiply everything left by b so each character moves up one power, and add the new character t[i+m] at power zero. That is the whole rolling update: h' = ((h - t[i]*b^(m-1)) * b + t[i+m]) mod p. The value b^(m-1) mod p is computed once before the scan, so each step costs one multiply-subtract, one multiply-add and a reduction. Putting the first character at the highest power is what keeps the update free of division; the reverse form needs a modular inverse.

A correct implementation

Here is a complete, verified implementation. The hash is a filter and the character comparison is the decision; the result never depends on the hash being collision-free. The base is drawn at random per run, for reasons the collision section makes precise. Python's % always returns a non-negative result, so the subtraction cannot leave a negative hash; in C, Java or Rust add p before reducing.

import secrets

P = (1 << 61) - 1                      # Mersenne prime, 2^61 - 1

def rabin_karp(text: str, pat: str) -> list[int]:
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    b = secrets.randbelow(P - 256) + 256   # random base, larger than the alphabet slice
    hi = pow(b, m - 1, P)                  # weight of the leftmost character
    hp = hw = 0
    for k in range(m):                     # Horner's rule for pattern and first window
        hp = (hp * b + ord(pat[k])) % P
        hw = (hw * b + ord(text[k])) % P
    out = []
    for i in range(n - m + 1):
        if hw == hp and text[i:i + m] == pat:   # verify every hash hit
            out.append(i)
        if i + m < n:
            hw = ((hw - ord(text[i]) * hi) * b + ord(text[i + m])) % P
    return out

Worked example by hand

Use small numbers so the arithmetic can be followed by hand: letters map to a=1 through z=26, the base is b=31, the modulus is p=101, and we search for the pattern "dab" in the text "abracadabra". The pattern hash is 4*31^2 + 1*31 + 2 = 3844 + 31 + 2 = 3877, and 3877 mod 101 = 39. The leftmost-character weight is 31^2 mod 101 = 961 mod 101 = 52.

The first window "abr" hashes to 1*961 + 2*31 + 18 = 1041, which is 31 mod 101. Rolling gives the sequence of window hashes below. Check one step yourself: going from "ada" (hash 76) to "dab", remove the leading a: 76 - 1*52 = 24; shift: 24*31 = 744; add b: 744 + 2 = 746; reduce: 746 mod 101 = 39. That matches the pattern hash, the three characters are compared, and position 6 is reported.

"abr" at positions 0 and 7 hashes equally, as equal strings must. With only 101 possible values, the chance that one of nine unrelated windows also hits 39 is near nine in a hundred, which is why real code uses a modulus near 2^61 and still verifies.

How often the hash lies

How often does the hash lie? Take two different strings x and y of the same length m. Their hashes are equal exactly when the polynomial D(b) = sum of (x[k] - y[k]) * b^(m-1-k) is zero modulo p. D is not the zero polynomial because the strings differ somewhere, and its degree is at most m - 1. A nonzero polynomial of degree at most m - 1 over the field of integers modulo p has at most m - 1 roots. So if b is chosen uniformly at random from the p possible values, the probability that x and y collide is at most (m - 1)/p.

Summed over all n - m + 1 windows, the expected number of spurious hits is at most (n - m + 1)(m - 1)/p. For a gigabyte of text, a 1,000-character pattern and p = 2^61 - 1, that is roughly 10^9 * 10^3 / 2.3 * 10^18, about 4 * 10^-7 spurious hits per scan. The expected verification cost is negligible and the worst case is guarded by the character comparison.

The guarantee is over the random choice of b, for every input. With a constant base in your source, an attacker can construct colliding strings and push the scan to O(nm). With a small prime, birthday arithmetic bites even without an attacker: near 10^9, expect a collision among tens of thousands of distinct strings, harmless for a verifying filter and fatal for code that equates hashes with strings.

Arithmetic without overflow

The modulus choice is an engineering decision as much as a mathematical one. In Python the integers are unbounded, so the code above is correct as written, just slower than native arithmetic. In a language with fixed-width integers, multiplying two 61-bit residues needs 122 bits. The standard answer is a 128-bit product and a Mersenne reduction, which replaces division with a shift, a mask and an add:

#include <stdint.h>
static const uint64_t M61 = (1ULL << 61) - 1;

static inline uint64_t mulmod61(uint64_t a, uint64_t b) {   /* a, b < M61 */
    __uint128_t x = (__uint128_t)a * b;
    uint64_t r = (uint64_t)(x & M61) + (uint64_t)(x >> 61);
    return r >= M61 ? r - M61 : r;
}

Why does one conditional subtraction suffice? Since 2^61 is congruent to 1 modulo 2^61 - 1, the high bits can be folded onto the low bits. Both inputs are below 2^61 - 1, so the product is below 2^122 - 2^62 + 1, the high part is at most 2^61 - 2, and the sum of the two parts is at most 2^62 - 3, which is less than twice the modulus. The __uint128_t type is a GCC and Clang extension; on MSVC use the _umul128 intrinsic or split the operands into 32-bit halves.

The tempting shortcut is to skip the modulus and let unsigned 64-bit arithmetic wrap, which is reduction modulo 2^64. Do not do this for anything that matters. Modulo a power of two the hash is not a field polynomial and the root-counting argument fails. With an even base, b^64 is zero, so every character more than 64 positions from the end of the window drops out entirely. For any odd base, the Thue-Morse string of length 2048 and its bitwise complement collide, which is a well-known way to break hash-based solutions in programming contests and an equally good way to break a deduplication service.

Variants: double hashing, many patterns, prefix hashes

Double hashing runs two independent hashes and treats the pair as the fingerprint, squaring the collision probability at twice the arithmetic. Use it when verification is impossible, for example when only hashes are stored; it does not replace verification when the text is available.

Multi-pattern search is where Rabin-Karp earns its keep. If you need any of k patterns that all share length m, put their hashes in a hash set and roll a single window over the text; each step is one rolling update and one set lookup, so the scan costs O(n + k*m) plus verification. Different lengths get one rolling pass each; with many distinct lengths, an Aho-Corasick automaton usually wins.

from collections import defaultdict

def find_any(text: str, patterns: list[str]) -> list[tuple[int, str]]:
    by_len = defaultdict(dict)                    # m -> {hash: [patterns]}
    b = secrets.randbelow(P - 256) + 256
    def h(s):
        v = 0
        for ch in s:
            v = (v * b + ord(ch)) % P
        return v
    for pat in set(patterns):
        if pat:
            by_len[len(pat)].setdefault(h(pat), []).append(pat)
    hits = []
    for m, table_ in by_len.items():              # one rolling pass per length
        if m > len(text):
            continue
        hi, hw = pow(b, m - 1, P), h(text[:m])
        for i in range(len(text) - m + 1):
            for pat in table_.get(hw, ()):
                if text.startswith(pat, i):       # verify
                    hits.append((i, pat))
            if i + m < len(text):
                hw = ((hw - ord(text[i]) * hi) * b + ord(text[i + m])) % P
    return sorted(hits)

Prefix hashes turn substring equality into an O(1) query. Store pre[i], the hash of the first i characters, and the powers of b. The hash of t[l:r] is then pre[r] - pre[l]*b^(r-l) modulo p. With that table you can binary-search for the longest repeated substring: a repeat of length L implies a repeat of every shorter length, so test a length by putting every window hash in a set and checking for a duplicate, verifying the candidate pair before accepting it. The result is O(n log n) expected time with a few lines of code. A suffix array with the LCP array answers the same question deterministically and supports many more queries, at the cost of more code.

Rabin fingerprints used for content-defined chunking in backup systems are a different construction, polynomials over GF(2), not the modular arithmetic here.

Failure modes

The bugs that ship are predictable, and most of them pass small tests.

• Trusting the hash. Code that reports a match on equal hashes without comparing characters is a probabilistic algorithm pretending to be exact. It will pass every unit test and fail rarely in production, or on demand for an attacker.
• Negative intermediate values. In C, Java and Go the subtraction step can go negative and the remainder operator keeps the sign, producing hashes that never match. Add the modulus before reducing.
• Overflow in the multiply. A 64-bit product of two residues near 2^61 overflows silently. Use a 128-bit product, a smaller modulus whose square fits, or a language with big integers.
• Constant or tiny parameters. A hard-coded base invites crafted collisions; a modulus near 10^9 collides by birthday arithmetic once you compare tens of thousands of strings without verification.
• Inconsistent character mapping. Hashing UTF-8 bytes for the pattern and code points for the text, or normalising one and not the other, gives silent misses. Decide the unit once and apply it everywhere.

Trade-offs and related reading

Use Rabin-Karp when the rolling hash is the point: many patterns of a few lengths, repeated-substring detection, fingerprints of sliding windows, or substring equality inside another algorithm. For one pattern searched once, KMP or the Z-algorithm give a guaranteed linear worst case with no randomness, and the library search in your language is usually faster still. When you store hashes as keys in a table, the advice in hash tables about keyed hashing against flooding applies equally to window fingerprints.

The cost model: O(m) preprocessing, O(n) hash steps and O(m) verification per hit, so O(n + m + m*occurrences). With dense true matches, such as all a's in all a's, verification makes it O(nm); KMP avoids that.

What to do next

1. Implement the single-pattern version above and test it against a naive matcher on random strings over a two-letter alphabet, where collisions and overlapping matches are frequent.
2. Shrink the modulus to 101 in a test build and confirm the output is unchanged while the verification count rises; that proves the hash is only a filter.
3. Port the roll to a fixed-width language with the Mersenne mulmod and test boundary values near 2^61 - 1.
4. Replace any constant base in existing code with a per-process random base, and remove any equality-by-hash shortcut that skips verification.
5. Build prefix hashes for one real string and implement longest repeated substring by binary search; compare its answer with a suffix-array solution.
6. For multi-pattern workloads, measure the hash-set approach against Aho-Corasick on your real pattern set before choosing.