Rolling Hashes & Rabin-Karp

The shape

You have a text of length n and a pattern of length k. The naïve search slides the pattern through the text and compares character-by-character at each position. O(n·k). For long patterns or many search queries, this is prohibitive. A rolling hash lets you compare candidates in O(1) per position, with a one-time O(k) hash of the pattern.

The trick is that we don't need to recompute the hash of each window from scratch. The hash of a substring shares almost all its work with the hash of the substring one position to the right; we can express the new hash as a constant-time update of the old one. That's the "rolling" part.

The hash function

Treat a string as a number in base B, where B is larger than the alphabet size (so each character maps to a distinct "digit"). For ASCII strings, B = 257 works; for Unicode, B = 1,000,003 or another sufficiently large prime. Take the result modulo a prime P to keep it in 64-bit range and avoid arithmetic overflow.

MOD = (1 << 61) - 1                  # Mersenne prime; plays well with Python ints
B   = 131                            # base > printable ASCII

def hash_string(s):
    h = 0
    for c in s:
        h = (h * B + ord(c)) % MOD
    return h

The choice of P matters. A small modulus produces frequent collisions. 2^61 − 1 is a Mersenne prime and gives ample range. For 32-bit languages, the contest convention is 10^9 + 7, which fits in a signed 32-bit int and has no special structure that adversaries can exploit.

Sliding the window

To shift from s[i..i+k) to s[i+1..i+1+k), we remove the contribution of s[i] from the leading position, then add s[i+k] at the trailing position. The leading character's contribution is s[i] · B^(k−1); precomputing B^(k−1) mod P once makes each shift O(1).

def rabin_karp(text, pattern):
    n, k = len(text), len(pattern)
    if k > n: return -1

    p_hash = 0
    t_hash = 0
    power  = 1                       # B^(k-1) mod P
    for i in range(k):
        p_hash = (p_hash * B + ord(pattern[i])) % MOD
        t_hash = (t_hash * B + ord(text[i])) % MOD
        if i < k - 1:
            power = (power * B) % MOD

    for i in range(n - k + 1):
        if t_hash == p_hash and text[i:i+k] == pattern:
            return i                 # verify on hit
        if i < n - k:
            t_hash = (t_hash - ord(text[i]) * power) % MOD     # remove leading
            t_hash = (t_hash * B + ord(text[i + k])) % MOD     # add trailing
    return -1

Two implementation choices. First, the verification step text[i:i+k] == pattern is essential, hash equality is necessary but not sufficient. With a good hash, hits are rare, so the verification cost is amortised O(1) per character on the whole input. Second, (t_hash - ...) % MOD can produce a negative intermediate in some languages; in Python the modulo always returns a non-negative result, but in Java or C++ you need to add MOD before taking the modulus.

Complexity, reasoned

Pattern hash: O(k). Initial text hash: O(k). Each shift: O(1). Total shifts: n − k + 1. Hash comparisons: O(1) each. Verification on a hit: O(k), but hits are rare under a good hash. Expected total: O(n + k). Worst case: O(n·k) under adversarial input that produces many false positives, a well-chosen prime and a randomised base eliminates this for non-adversarial inputs.

This is competitive with KMP (O(n + k) deterministic). Rabin-Karp is generally easier to extend (multiple patterns, 2D matching, long pattern preprocessing) but has the verification overhead and the hash-collision risk.

Multiple patterns at once

Want to find any of m patterns? Hash each pattern (O(m·k) total), insert the hashes into a set, then run a single rolling hash over the text. At each window, ask "is this hash in the set?", one hash-set lookup per shift. O(n + m·k) total. Compare to naïve: O(n·m·k). The win grows with m.

Adversarial input, double hashing

A determined adversary can construct strings whose hashes collide under any single fixed prime. The fix is to compute two independent hashes (different bases, different primes) and consider two windows equal only if both hashes match. The probability of a coincidental two-way collision is tiny (1 / (P₁ · P₂), typically < 10^−18).

def double_hash(s, B1=131, P1=(1<<61)-1, B2=137, P2=998244353):
    h1 = h2 = 0
    for c in s:
        h1 = (h1 * B1 + ord(c)) % P1
        h2 = (h2 * B2 + ord(c)) % P2
    return (h1, h2)

Use double hashing in competitive-programming submissions and content-addressable storage; single hashing is fine for one-off scripts and casual use.

Generalisations

2D pattern matching

Given an h × w pattern and an H × W image (or grid of characters), find all occurrences. Compute a rolling hash horizontally for each row of the image, then a rolling hash vertically over the row hashes. Total: O(H · W) preprocessing, O(H · W) matching.

Longest duplicate substring

Binary search on the length L. For each candidate L, hash every length-L substring of the text. If any hash repeats, the longest duplicate is at least L. O(n log n) total, see the Sorting & Search module's "binary search on the answer" pattern.

Detecting near-duplicates

Hash sliding windows of a document at multiple offsets, store the smallest k hashes (a "min-hash"). Documents that share many min-hashes are near-duplicates. The technique scales to billions of documents.

When to reach for it

• Many patterns vs one text, rolling hash with a hash-set lookup at each window beats KMP's per-pattern preprocessing.
• Long patterns where you'd rather not implement KMP's failure function, Rabin-Karp's code is much shorter.
• Substring problems that need fingerprints, not just locations, compiler intern tables, plagiarism, fuzzy matching.
• 2D or higher-dimensional matching, the rolling-hash idea generalises directly; KMP does not.

Reach for KMP when the input is adversarial and you cannot afford even rare worst cases, or when memory is tight and you want a single-pass algorithm with no auxiliary table beyond the failure function.

Where beginners go wrong

• Skipping the verification step. Hash equality does not guarantee string equality. Without verification, the algorithm produces false positives.
• Using a small modulus. 10⁹ looks large, but for 100,000 substrings the birthday-paradox collision rate is ~0.5%. Use 2^61 − 1 in Python or double hashing in 32-bit languages.
• Forgetting to add MOD before the negative modulo. In C++/Java, (a - b) % P can be negative. Use ((a - b) % P + P) % P.
• Re-computing B^(k−1) each iteration. The power is constant; precompute it once. Re-computing turns O(n) into O(n·k) and defeats the whole point.
• Choosing B smaller than the alphabet. If B ≤ alphabet size, two different characters can produce the same digit and hashes silently collide.

What to read next

The Strings module covers KMP's failure function as the deterministic alternative. Sliding Window in Depth shares the "constant-time window update" structure. And the Sorting & Search module's binary-search-on-answer pattern combines with rolling hashes for the longest-duplicate-substring problem.