Rabin-KarpRolling hash matching

01Why it exists

Reach for it when you see:Finding fixed-length fragments in a long text, searching for many equal-length patterns at once, comparing every length-k substring, needing a fingerprint each time the window moves one place, expected linear time being good enough.

02The core idea

Brute-force matching compares character by character from every starting position, O(nm) in the worst case: with a text of a million a's and a pattern of 999 a's followed by a b, every start has to reach the last character before it fails. Rabin-Karp's idea is to compare hashes first. Hash the pattern P once, hash every length-m window of the text T, and skip immediately whenever the two differ, because different hashes guarantee different strings. But recomputing a window from scratch costs O(m), which leaves the total at O(nm), so the whole trick is making the hash roll.

A rolling hash reuses the polynomial hash from the previous lesson and treats the window as an m-digit number in base B. To slide one place right: subtract the top digit T[i]·B^(m−1), multiply by B to push everything up a place, then add the incoming T[i+m]. That is hash(i+1) = (hash(i) − T[i]·B^(m−1))·B + T[i+m], all mod M. In decimal, sliding a four-digit window from 1234 to 2345 is (1234 − 1 × 1000) × 10 + 5. With B^(m−1) computed in advance, each position costs a handful of additions and multiplications, so O(1).

Equal hashes do not mean equal strings, so every candidate needs a character-by-character check, and the ones that fail it are false positives caused by collisions. Complexity: O(m) for P and the first window, then O(1) for each of the n − m + 1 slides; each verification is O(m), but a false positive has probability around 1/M and is essentially never seen with a large enough modulus, so the expected time is O(n + m + number of hits × m). When the question is only whether the pattern occurs at all, you stop at the first hit, which is an expected O(n + m). The worst case is still O(nm): a pattern that overlaps itself all over the text (T all a's, P all a's), or a modulus and base that someone has guessed and used to construct collisions deliberately. The extra space is a few integers, O(1).

Common traps: subtracting the top digit can go negative, so C++ has to add M first; recomputing B^(m−1) inside the loop turns every position back into O(m); skipping the character-by-character check makes collisions report positions that are not matches; and once the last window has slid, do not read T[i+m] again or you run off the end. When the alphabet is small and the pattern short, encode each character in a fixed number of bits (2 bits per DNA base) and the rolling value becomes a collision-free encoding. How this relates to the neighbouring lessons: the previous lesson's prefix hash can compare every window too, via get(i, i+m), but it needs O(n) space where the rolling version needs O(1); single-pattern matching with a guaranteed worst case of O(n + m) is the next lesson, KMP; and large numbers of patterns of differing lengths belong to Aho–Corasick on a trie.

03The algorithm

1. 1Return straight away if the pattern is longer than the text. Compute hash(P) and the first window's hash(T[0, m)), and precompute top = B^(m−1) mod M.
2. 2Check the current window i: if its hash differs from hash(P), skip it, because it cannot possibly match.
3. 3On a hash match, compare T[i, i+m) with P character by character, and record position i only if every character agrees; a mismatch is a collision, so move on.
4. 4Unless this is the last window, roll: hash = ((hash − T[i]·top)·B + T[i+m]) mod M, adding M first if the subtraction would go negative.
5. 5Repeat until i = n − m. With several patterns of the same length, put their hashes in a hash table and do one lookup per window.

04Interactive demo

Searching for P = abra in T = abracadabra, with B = 31 and a = 1 as in the previous lesson and a deliberately tiny modulus M = 101. hash(P) = 53, and the weight of the top digit is 31³ mod 101 = 97. Yellow is the current window; on each slide, grey is the character that just left and blue the one that just arrived, with the O(1) rolling formula shown in the box. The eight windows hash to 53, 53, 74, 86, 64, 35, 15 and 53 in order: window 0 matches on hash, turns green once the character-by-character check passes, and is a genuine hit; window 1 holds brac, which also hashes to 53, but the very first character disagrees during verification and is marked in blue — that is a collision; the five in the middle have different hashes and are skipped outright; window 7 hits again. The answer is positions 0 and 7.

05Code

Python has single-pattern Rabin-Karp plus a version that shares one scan between several equal-length patterns, both verifying character by character after a hash match. C++ has the single-pattern version, adding M before subtracting because the arithmetic is unsigned, along with the 2-bit rolling encoding for DNA fragments: with only 4 letters the rolling value cannot collide at all, so no modulus is needed.

import random

M = 1_000_000_007
B = random.randrange(256, M)            # pick the base at random so nobody can construct collisions in advance


def poly_hash(s):
    x = 0
    for ch in s:
        x = (x * B + ord(ch)) % M
    return x


def rabin_karp(text, pat):
    """Every position where pat occurs in text. Each window updates in O(1), so O(n + m) expected."""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    top = pow(B, m - 1, M)              # weight of the window's top digit, used to subtract the character that leaves
    hp, hw = poly_hash(pat), poly_hash(text[:m])
    res = []
    for i in range(n - m + 1):
        if hw == hp and text[i:i + m] == pat:   # only verify character by character on a hash match; collisions stop here
            res.append(i)
        if i + m < n:                   # drop the top digit, shift left one place, add the incoming character
            hw = ((hw - ord(text[i]) * top) * B + ord(text[i + m])) % M
    return res


def find_many(text, patterns):
    """Several patterns of the *same length* at once: their hashes go in a dict and the text is scanned once."""
    m = len(patterns[0])
    if m == 0 or m > len(text):
        return []
    table = {}
    for p in patterns:
        table.setdefault(poly_hash(p), []).append(p)
    top = pow(B, m - 1, M)
    hw, res = poly_hash(text[:m]), []
    for i in range(len(text) - m + 1):
        for p in table.get(hw, []):     # one hash value can hold several patterns, so verify each of them
            if text[i:i + m] == p:
                res.append((i, p))
        if i + m < len(text):
            hw = ((hw - ord(text[i]) * top) * B + ord(text[i + m])) % M
    return res


if __name__ == "__main__":
    print(rabin_karp("abracadabra", "abra"))    # [0, 7]
    print(rabin_karp("aaaaa", "aa"))            # [0, 1, 2, 3]
    print(find_many("ACGTTGCAACGTAGGT", ["ACGT", "AGGT", "TTTT"]))
    # [(0, 'ACGT'), (8, 'ACGT'), (12, 'AGGT')]

06Practice

• LeetCode 796Rotate String (look for goal inside s + s)Easy
• LeetCode 1461Check If a String Contains All Binary Codes of Size K (roll a window of bits)Medium
• LeetCode 187Repeated DNA Sequences (2-bit rolling encoding)Medium
• LeetCode 686Repeated String MatchMedium
• LeetCode 2156Find Substring With Given Hash Value (roll the other way, right to left)Hard
• LeetCode 1923Longest Common Subpath (binary search the length, intersect each path's rolling hashes)Hard