Rabin-Karp and Rolling Hashes

Fix an alphabet of size at most $d$ (e.g., $d = 256$ for bytes) and treat a string $s = s_0 s_1 \cdots s_{m-1}$ as a base-$d$ number:

This is a polynomial hash: the string's characters are the coefficients (or digits) of a degree-$(m-1)$ polynomial evaluated at $x = d$. Because real hash values would overflow for long strings, we work modulo a prime $q$, computing $H(s) \bmod q$. Two different strings can then collide — hash to the same residue — even though they are not equal; such a false alarm is called a spurious hit, and it is the price paid for speed. This is the same collision phenomenon studied in Introduction to Hashing, specialized to strings with polynomial structure instead of arbitrary keys. The property that makes this hash exploitable for string search is that consecutive windows of the text overlap in $m - 1$ characters. If $t_i = t_i t_{i+1} \cdots t_{i+m-1}$ is the window starting at position $i$, then $t_{i+1}$ is obtained from $t_i$ by dropping the leading character and appending one new character. Because $H$ is a linear (affine) function of the digit sequence, this shift corresponds to simple modular arithmetic — subtract off the leading digit's contribution, shift everything up by one power of $d$, and add the new trailing digit. That is the rolling hash update, and it costs O(1) modular multiplications and additions, independent of $m$. Rabin-Karp is then: compute the pattern's hash once; compute the hash of the first text window; slide across the text, at each step comparing the rolling hash of the current window against the pattern's hash; whenever hashes match, verify with a direct character comparison (since a match could be spurious); report true matches. This converts an O(nm) brute-force scan (see Naive String Matching and the Matching Problem) into an algorithm whose expected cost is linear in the input size, provided the modulus is chosen well.

Setup. Let $n = |T|$ (text length), $m = |P|$ (pattern length), alphabet size $d$, and modulus $q$ a prime (ideally larger than $\max(d, m)$ and, for practical purposes, large enough that $d \cdot q$ fits in a machine word to avoid overflow during the update).

Precompute. Compute $h = d^{m-1} \bmod q$ once; this is the weight of the leading digit that must be peeled off on each slide.

Initialize. Compute $H(P) \bmod q$ and $H(T[0..m-1]) \bmod q$ directly, each in O(m) time, using Horner's rule.

Slide. For each window start $i$ from $0$ to $n - m$: 1. If the current window's hash equals the pattern's hash, verify with a direct string comparison (O(m) worst case, but this branch is rarely taken if $q$ is large and random). 2. Unless this is the last window, update the hash in O(1):

Care is needed with the subtraction, since modular arithmetic in most languages does not automatically keep values nonnegative; add $q$ before taking the remainder if needed. ``` function RABIN-KARP-MATCH(T, P, d, q): n = length(T) m = length(P) if m == 0 or m > n: return [] // no valid window matches = [] // h = d^(m-1) mod q, the place-value of the leading digit h = 1 for i = 1 to m - 1: h = (h d) mod q // Compute initial hashes of P and T[0..m-1] via Horner's rule p_hash = 0 t_hash = 0 for i = 0 to m - 1: p_hash = (p_hash d + value(P[i])) mod q t_hash = (t_hash d + value(T[i])) mod q for s = 0 to n - m: // s = candidate start index if p_hash == t_hash: // hash match: could be a true match or a spurious collision if T[s .. s+m-1] == P: // O(m) direct verification matches.append(s) if s < n - m: // roll the hash forward by one character leading = value(T[s]) h mod q t_hash = ((t_hash - leading) d + value(T[s + m])) mod q t_hash = (t_hash + q d) mod q // guard against negativity // (adding a multiple of q * d before mod is a safe fix; // simpler implementations add q once per subtraction step) return matches ``` `value(c)` maps a character to an integer in $[0, d)$, e.g. its ASCII/byte code. The comment about negativity matters in practice: after subtracting `leading`, the intermediate value can be negative in languages whose `mod` can return negative results (C, Java, Python's `%` is fine but C's is not) — always normalize back into $[0, q)$.

Time complexity. Precomputing $h$, $p\_hash$, and the initial $t\_hash$ takes O(m). The main loop runs $n - m + 1$ times, and each iteration does O(1) work for the rolling update plus a hash comparison. If the hashes never collide (or collide only when the strings are truly equal), verification never runs on a false candidate, and the total cost is

This is the best case and, with a well-chosen modulus, the expected case. The worst case is different and important to state honestly: if every window happens to hash to the same value as the pattern (which an adversary can engineer, or which happens with a poorly chosen small modulus), the algorithm performs a full O(m) verification at every one of the $O(n)$ positions, giving $O(nm)$ — no better than naive matching. Rabin-Karp's practical value rests entirely on the modulus being large enough, and ideally random enough, that this worst case is exceedingly unlikely for real inputs.

Space complexity is O(1) beyond the input and the output list of match positions — only a constant number of integers ($h$, the two rolling hashes, loop counters) are maintained, in contrast to automaton-based matchers like Knuth-Morris-Pratt, which build an O(m)-size failure table.

Correctness argument. Correctness has two parts: soundness (every reported match is real) and completeness (every real match is reported). Completeness. The algorithm examines every window position $i \in \{0, \dots, n-m\}$ exactly once (this is the loop invariant: at the top of iteration $s$, `t_hash` equals $H(T[s..s+m-1]) \bmod q$, provable by induction using the rolling-update identity below). Whenever the true pattern occurs at position $i$, $T[i..i+m-1] = P$ so certainly $H(T[i..i+m-1]) \bmod q = H(P) \bmod q$; the hash comparison at that position will succeed, triggering verification, which will confirm the true match and record it. No real occurrence is skipped. Soundness. A position is only added to `matches` after the direct character-by-character comparison `T[s..s+m-1] == P` succeeds. This comparison is exact, not probabilistic, so no false positive can ever be reported — the algorithm never sacrifices correctness for speed, only the time spent verifying is affected by hash collisions. Correctness of the rolling update itself. Write $T[i..i+m-1]$'s value as

Then

which is exactly the formula used (verify by expanding the sum and matching powers of $d$ — subtracting the leading term removes $T[i]\cdot d^{m-1}$, multiplying by $d$ shifts every remaining term up one power, and adding $T[i+m]$ inserts the new low-order digit). Taking everything mod $q$ preserves this identity because modular arithmetic commutes with addition, subtraction, and multiplication.

Spurious-hit analysis (why the expected time is linear). Fix the modulus $q$ as a randomly chosen prime from a suitable range, say among primes up to $m^2 \log m$ or larger (a common convention in the analysis). For a fixed pair of unequal windows of length $m$ over an alphabet of size $d$, their two integer values differ, and their difference is bounded by $d^m$. A nonzero integer bounded by $d^m$ has at most $\log_2(d^m) = m\log_2 d$ distinct prime factors (since a number this size cannot have more than that many distinct prime divisors, as the product of the first $k$ primes already exceeds any polynomial bound once $k$ grows past $O(m \log d / \log(m\log d))$ — informally, the number of "bad" primes that make two specific unequal windows collide is at most $O(m \log d)$). If $q$ is drawn uniformly from the primes up to some bound $Q$, and there are $\pi(Q) \approx Q/\ln Q$ such primes by the prime number theorem, the probability that a specific unequal window collides with the pattern under a random $q$ is at most

Choosing $Q$ polynomially larger than $m$ (e.g. $Q = \Theta(m^2 \log d)$) makes this probability $O(1/m)$ per position. Summing over all $n$ positions, the expected total number of spurious hits is $O(n/m) \cdot 1 = O(n \cdot \frac{1}{m}\cdot m)$ — more precisely the standard result is that the expected number of spurious matches, and hence extra verification steps, is $O(n/q)$ for $q$ chosen at least as large as $m$, which is O(1) amortized per window when $q = \Omega(n)$, or a small constant total when $q$ is a large fixed prime. The clean informal takeaway: make $q$ a large prime, ideally exceeding the number of windows you will ever hash, and spurious hits become rare enough that expected total verification cost is $O(m)$ overall rather than $O(nm)$. The important honesty here: this is a statement about a randomly chosen modulus against a fixed input, or equivalently a fixed modulus against inputs not adversarially constructed against it. If an adversary knows the fixed $q$ used by an implementation (many textbook implementations hardcode $q$), they can construct a text where every window collides with the pattern's hash, forcing the $O(nm)$ worst case. This is precisely the setting where Introduction to Randomized Algorithms becomes relevant: choosing $q$ randomly at runtime, unknown to any adversary in advance, restores the expected-linear-time guarantee even against adversarial inputs — this is the same idea as universal hashing.

Trade-offs versus alternatives. Knuth-Morris-Pratt and Z-algorithm guarantee O(n + m) worst-case time deterministically, with no dependence on hash luck, but require building and reasoning about a failure function or Z-array. Rabin-Karp's real strength is not single-pattern matching in isolation — it is multi-pattern matching: hashing lets you check membership in a large set of pattern hashes in O(1) per window (via a hash set of pattern hashes), giving an easy path to searching for thousands of patterns simultaneously, which is awkward for KMP without building an Aho-Corasick automaton. Rabin-Karp is also the natural building block whenever you need fingerprints of substrings for reasons beyond exact matching — plagiarism detection, deduplication, and rsync-style diffing all want a compact, quickly updatable signature of a window, not just a yes/no match.

Search for pattern `P = "ana"` in text `T = "banana"`, using $d = 256$ (treating characters as ASCII codes) is unwieldy to trace by hand, so instead use small illustrative numeric values: alphabet $\{a, b\} \to \{1, 2\}$, base $d = 10$, modulus $q = 13$, so we can track every arithmetic step. Text: `T = b a n a n a` → using $a=1$, $b=2$, and (for the letter n, not in our tiny alphabet) let's simplify further to the classic textbook example instead, matching CLRS-style small numbers.

Concrete numeric trace. $T = 2359023141$, $P = 31415$ (treat these as strings of decimal digits), $d = 10$, $q = 13$. We search for occurrences of `31415` in `2359023141`. $n = 10$, $m = 5$. Step 1 — precompute $h = d^{m-1} \bmod q = 10^4 \bmod 13$. $10^1=10,\ 10^2=100\equiv 9,\ 10^3\equiv 90\equiv 12,\ 10^4\equiv 120\equiv 3 \pmod{13}$. So $h = 3$. Step 2 — hash the pattern $P = 31415$ directly: $31415 \bmod 13$. $31415 = 13\times 2416 + 7$, so $p\_hash = 7$. Step 3 — hash the first window $T[0..4] = 23590$: $23590 \bmod 13$. $13 \times 1814 = 23582$, remainder $8$. So $t\_hash = 8$. Now slide across all windows, comparing hashes and rolling forward:

Rolling from $s=0$ to $s=1$: drop $T[0]=2$, shift, append $T[5]=0$.

Interesting: $t\_hash = 7$ here matches $p\_hash = 7$! This is a spurious hit — window `35902` hashes the same as `31415` under this small modulus but is not equal to it. The algorithm must verify: compare `35902` to `31415` character by character; they differ at the first character (`3` matches, `5` vs `1` differs), so verification correctly rejects it in O(1) actual comparisons here (fails fast). This single trace already demonstrates why verification is not optional — without it, the algorithm would have incorrectly reported a match at $s=1$. Continue rolling to $s=2$: drop $T[1]=3$, append $T[6]=2$.

$t\_hash = 8 \ne 7$: no match, correctly, since `59023 ≠ 31415`. $s=3$: drop $T[2]=5$, append $T[7]=1$.

No match (`90231 ≠ 31415`), consistent. $s=4$: drop $T[3]=9$, append $T[8]=4$.

$-176 \bmod 13$: $13\times(-14) = -182$, so $-176-(-182)=6$. $t\_hash = 6 \ne 7$. No match (`02314 ≠ 31415`), consistent. $s=5$: drop $T[4]=0$, append $T[9]=1$.

recompute carefully: $61 \bmod 13 = 61 - 4\times13 = 61-52 = 9$. Hmm — that gives $9 \ne 7$, but the true window at $s=5$ is $T[5..9]=23141$, not $31415$; note the true window is `23141`, which indeed is not equal to the pattern `31415` — so a mismatch here is correct, not an error, since the pattern doesn't actually occur at $s=5$ either. (This tiny 10-digit example was chosen to demonstrate the mechanics and a spurious hit, not to guarantee a genuine occurrence exists — direct inspection confirms `31415` does not literally occur as a contiguous digit substring of `2359023141`.) The important pedagogical content is intact: we saw the initial hash computation, five correct O(1) rolling updates, one true negative avoided correctly, and one spurious hit at $s=1$ correctly caught and rejected by verification — exactly the behavior the correctness argument predicts.

Michael O. Rabin and Richard M. Karp jointly designed the algorithm and published it in 1987, though the underlying idea of using randomized fingerprints to test string equality traces back to Rabin's earlier work on fingerprinting for verifying equality of large data efficiently. Both were already towering figures: Rabin (with Dana Scott) had earlier formalized nondeterministic automata, and Karp had built much of the foundational theory of NP-completeness reductions. Their string-matching algorithm exemplifies a broader theme in their careers — replacing exact, expensive deterministic checks with cheap randomized ones that are correct with overwhelming probability, and can be made fully correct by adding a cheap verification step.

Version control and file synchronization. The rsync algorithm uses a rolling checksum (a variant closely related to Rabin-Karp's hash) to find which blocks of a file have changed without transferring the whole file, by sliding a window and comparing rolling hashes against a table of block hashes from the remote copy.

Deduplication and content-defined chunking. Distributed storage and backup systems (e.g., systems built around Rabin fingerprinting) use rolling hashes to decide chunk boundaries based on content rather than fixed offsets, so that inserting a byte near the start of a file does not shift every subsequent chunk boundary — critical for deduplication ratios.

Plagiarism and code-clone detection. Systems that fingerprint overlapping k-grams of text or code (related to the MOSS and Winnowing algorithms) rely on fast rolling hashes to make scanning millions of documents computationally feasible.

Bioinformatics. Searching for short motifs or exact repeats in long genomic sequences benefits from Rabin-Karp-style hashing, especially when many patterns must be checked against one long text simultaneously, since a hash table of pattern hashes turns multi-pattern search into near-constant work per window.

Multi-pattern and streaming search. Because Rabin-Karp compares hashes rather than running a separate automaton per pattern, it naturally extends to checking membership in a large dictionary of pattern hashes at each window — a common building block before falling back to more specialized automata like Aho-Corasick for guaranteed worst-case behavior. It also builds the intuition needed for Introduction to Randomized Algorithms, where choosing structure (like a modulus, or a hash function) at random defeats adversaries who cannot predict the random choice.

Ask the tutor: How does choosing the modulus randomly at runtime formally restore Rabin-Karp's expected linear-time guarantee even against adversarially constructed text?