Rabin-Karp Algorithm

The Rabin-Karp algorithm is a randomized substring and multi-pattern search method in computation and algorithms that reduces character-block comparisons to constant-time integer comparisons using a polynomial rolling hash (the Rabin fingerprint). Introduced by Richard M. Karp and Michael O. Rabin in the IBM Journal of Research and Development in March 1987, the algorithm computes an arithmetic hash value p for the pattern P[0..m − 1] and maintains a sliding-window hash value t_s for each length-m substring T[s..s + m − 1] of the text T[0..n − 1]. Because advancing the window by one position removes only the leading character T[s] and appends the trailing character T[s + m], the new hash t_s+1 is updated from t_s in O(1) arithmetic operations without re-scanning the m − 1 interior characters.

Whereas the Knuth-Morris-Pratt algorithm and Boyer-Moore string-search algorithm rely on structural border and suffix tables tailored to a single one-dimensional pattern, the algebraic linearity of the Rabin-Karp rolling hash generalizes naturally to simultaneous multi-pattern dictionary search (often paired with a hash table or Bloom filter), two-dimensional m × m matrix pattern matching, content-defined file chunking (as in rsync and deduplicating storage engines), and high-throughput k-mer minimizer sketching in bioinformatics.

Modular Polynomial Representation of Strings

Let Σ be an alphabet of radix d = |Σ| (for example, d = 256 for 8-bit ASCII bytes or d = 4 for the DNA alphabet {A = 0, C = 1, G = 2, T = 3}). The Rabin-Karp algorithm treats any length-m string S[0..m − 1] as an m-digit integer written in base d:

V(S) = S[0] · d^m−1 + S[1] · d^m−2 + ··· + S[m − 2] · d¹ + S[m − 1] · d⁰ = ∑_j=0^m−1 S[j] · d^m−1−j

When m exceeds 32 or 64 characters, V(S) overflows a native CPU machine word. To keep all intermediate quantities within single-word registers (where addition and multiplication execute in O(1) clock cycles), all arithmetic is performed modulo a prime number q chosen such that d · q fits comfortably within a 64-bit integer word. Using Horner's rule, the initial pattern hash p = V(P) mod q and the initial text window hash t₀ = V(T[0..m − 1]) mod q are evaluated in Θ(m) time:

1. Initialize p ← 0 and t₀ ← 0.
2. Precompute the high-order multiplier h ← d^m−1 mod q.
3. For j = 0 to m − 1:
   • p ← (d · p + P[j]) mod q
   • t₀ ← (d · t₀ + T[j]) mod q

Constant-Time O(1) Sliding-Window Update

Once t_s is known for the window T[s..s + m − 1] (for 0 ≤ s < n − m), shifting the window one character to the right yields T[s + 1 .. s + m]. In base-d arithmetic, this shift subtracts the highest-order term T[s] · d^m−1, multiplies the remaining (m − 1)-digit integer by d, and adds the new lowest-order digit T[s + m]. Reducing modulo q gives the Rabin-Karp rolling recurrence:

t_s+1 = ( d · (t_s − T[s] · h) + T[s + m] ) mod q

where h = d^m−1 mod q is precomputed once before the loop. In unsigned modular arithmetic, if t_s − (T[s] · h mod q) is negative, adding q restores a non-negative residue in {0, 1, ..., q − 1}. Each window transition therefore requires only two modular multiplications, one subtraction, and one addition—Θ(1) time independent of pattern length m.

Concrete Numeric Walkthrough

Consider base d = 10 over digit strings, modulus q = 101, pattern P = "31415" (m = 5), and multiplier h = 10⁴ mod 101 = 10,000 − 99 × 101 = 1:

• Pattern value: V("31415") = 31,415 = 311 × 101 + 4, so pattern hash p = 4.
• Suppose the current text window at shift s is T[s..s + 4] = "23141" with hash t_s = 23,141 mod 101 = 12, and the incoming character is T[s + 5] = 5.
• Applying the rolling recurrence:

t_s+1 = (10 · (12 − 2 · 1) + 5) mod 101 = (10 · 10 + 5) mod 101 = 105 mod 101 = 4.

• Because t_s+1 = 4 = p, the fingerprint matches at shift s + 1 ("31415").

Hash Collisions (Spurious Hits)

Because the space of all possible length-m strings has size d^m ≫ q, the pigeonhole principle implies that two distinct strings T[s..s + m − 1] ≠ P can map to the identical residue t_s = p (mod q). Such a false-alarm collision is called a spurious hit.

In computational complexity theory, randomized algorithms are divided into Las Vegas and Monte Carlo paradigms, and Rabin-Karp can be operated in either regime:

Bound on Spurious Hits via Prime Number Theory

Why do Karp and Rabin choose the modulus q uniformly at random from the prime numbers in the interval [2, Q]? Suppose a window T[s..s + m − 1] ≠ P produces a spurious hit (t_s = p mod q). Then the non-zero integer difference:

Δ_s = |V(T[s..s + m − 1]) − V(P)|, with 1 ≤ Δ_s < d^m

must be divisible by the prime q. Because any positive integer Δ_s < d^m can have at most log₂(Δ_s) < m log₂ d distinct prime factors, and the Prime Number Theorem guarantees at least π(Q) ≈ Q / ln Q primes below Q, the probability that a randomly selected prime q ≤ Q divides Δ_s is at most:

Pr(t_s ≡ p mod q | T[s..s + m − 1] ≠ P) ≤ (m log₂ d) / π(Q)

Summing over all n − m + 1 text windows via the union bound, choosing a 64-bit random prime q ≈ 2⁶¹ − 1 (the Mersenne prime 2,305,843,009,213,693,951, for which modular reduction executes via bitwise shifts and additions without hardware division) reduces the false-positive collision probability per window to less than 10⁻¹⁶.

Multi-Pattern Matching and 2D Submatrix Search

When searching for a dictionary of k patterns {P₁, P₂, ..., P_k} of common length m, single-pattern algorithms like Boyer-Moore must scan the text k times unless compiled into an Aho-Corasick automaton of size Θ(km |Σ|). Rabin-Karp instead hashes all k patterns in O(km) time into a hash table or Bloom filter and slides a single length-m rolling window across T, testing membership in O(1) expected time per position for a total expected runtime of O(n + km).

Similarly, to locate an m × m pattern matrix inside an n × n image array, Rabin-Karp computes 1D rolling hashes along each column of height m and then applies a second horizontal rolling hash across m adjacent column hashes, completing the 2D search in O(n²) expected time rather than O(n²m²).

Content-Defined Chunking (CDC) and Genomic k-mer Sketching

Two major modern systems domains rely directly on Rabin-Karp rolling hashes:

1. Content-Defined Chunking in File Synchronization and Deduplication: If a single byte is inserted at the start of a 10 GB file, fixed-size 4 KB block hashes change across the entire file. Utilities such as rsync, the Low-Bandwidth Network File System (LBFS), and deduplicating backup stores instead slide a 48-byte Rabin fingerprint (originally formulated by Rabin in 1981 over irreducible polynomials in GF(2⁶⁴)) across the byte stream and declare a chunk boundary whenever the lowest 13 bits of the rolling hash equal a target mask (t_s mod 2¹³ = 0). Because chunk boundaries are anchored to local content rather than fixed byte offsets, an insertion alters only the single chunk containing the edit.
2. Genomic k-mer Hashing and Minimizer Sketching: In high-throughput sequence alignment (such as Minimap2 by Heng Li) and metagenomic taxonomic classification (Kraken 2), sequencing reads are decomposed into overlapping k-mers (typically k = 15 to 31). Cyclic polynomial rolling hashes (ntHash) compute both the forward and reverse-complement k-mer hashes in O(1) time per base, selecting the lexicographically or numerically smallest hash in each window (minimizer) to index gigabase genomes in compact hash tables.

How does polynomial rolling hash differ from cyclic polynomial (Buzhash / ntHash) rolling hash?

The classic Rabin-Karp hash multiplies by radix d modulo a prime q (t_s+1 = (d(t_s − T[s]h) + T[s+m]) mod q). Cyclic polynomial hashes (Buzhash and ntHash) replace modular multiplication and addition with 1-bit circular bitwise barrel-rotations (ROL) and bitwise exclusive-OR (XOR) over a 64-bit random lookup table, eliminating integer multiplication and prime modular reduction.

Why is the modulus q chosen to be a prime number?

Choosing a prime modulus q that is coprime to the alphabet radix d ensures that every character position weight d^m−1−j mod q is non-zero and invertible in the finite field Z/(*q*Z). If q were a power of two (such as 2⁶⁴) and d were even (such as d = 256), then d^k mod 2⁶⁴ = 0 for all k ≥ 8, erasing the contribution of all characters more than 8 positions from the right end of the window.

1. Karp, R. M., & Rabin, M. O. (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2), 249–260. https://doi.org/10.1147/rd.312.0249
2. Muthitacharoen, A., Chen, B., & Mazières, D. (2001). A low-bandwidth network file system. ACM SIGOPS Operating Systems Review, 35(5), 174–187. https://doi.org/10.1145/502059.502052
3. Mohamadi, H., Chu, J., Vandervalk, B. P., & Birol, I. (2016). ntHash: Recursive nucleotide hashing. Bioinformatics, 32(22), 3492–3494. https://doi.org/10.1093/bioinformatics/btw397
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). String Matching: The Rabin-Karp Algorithm. In Introduction to Algorithms (3rd ed., pp. 990–995). MIT Press. https://doi.org/10.1016/B978-0-12-803738-6.00012-4