Rabin Karp algorithm: Definition & Examples

The Rabin–Karp algorithm searches for a contiguous sequence by comparing the pattern's hash with a rolling hash of the text. When the hashes agree, the exact version compares the symbols themselves. A quant developer could use this to find where a known sequence of message types recurs in a long feed replay. To find sequences of consecutive feed messages, scan in feed order within each stream and break the search at unresolved sequence gaps.

Roll the hash forward by one symbol

Encode symbols as integers and use the same encoding for the text and pattern. For a pattern of length $m$ , let $x_i$ be the encoded text symbol at zero-based index $i$ . The hash of the window starting there is

H_i=\left(\sum_{j=0}^{m-1}x_{i+j}b^{m-1-j}\right)\bmod q,

where

b

is the polynomial base and

q

is the modulus. Initialise the pattern hash and the first window hash by multiplying the running residue by

b

, adding the next symbol and taking the remainder. Then use a fixed-length sliding window. With

B=b^{m-1}\bmod q

precomputed, each shift removes the outgoing symbol's contribution, multiplies the remainder by

b

to shift the retained symbols one place and appends the new symbol. MIT 6.006 recitation notes

H_{i+1}=\bigl(b(H_i-x_i B)+x_{i+m}\bigr)\bmod q.

Keep residues between

0

and

q-1

, even if the subtraction makes the intermediate value negative. Different hashes rule out equality. Equal hashes identify a candidate, and direct comparison decides whether it is a match. Karp and Rabin (1987), Sections 2 and 4

Two hash hits, one exact match

Search the toy text 0012 for 12 with base

3

and modulus

5

. The pattern hash is

(1\cdot3+2)\bmod5=0

. The first window, 00, also hashes to

0

, but its first digit differs from the pattern's. Rolling right to 01 gives

(3(0-0\cdot3)+1)\bmod5=1

, so that window needs no comparison. Rolling once more to 12 gives

(3(1-0\cdot3)+2)\bmod5=0

. Both digits now agree, so index

2

is the only exact match. The tiny modulus makes the collision visible.

Text 0012 has three length-two windows with hashes 0, 1 and 0. Start 0 is a rejected collision, start 1 is screened out by its hash, and start 2 is a confirmed match.

Each row shifts the two-digit window one position to the right. Only the rows with hash 0 reach direct comparison.

When the scan is linear

With constant-time modular arithmetic and indexed access to the text, hashing a pattern and scanning a text of length $n$ takes $O(n+m)$ before direct comparisons. If $C$ windows reach direct comparison, the total cost is $O(n+m+mC)$ . The scan stays linear if the direct comparisons together cost $O(n+m)$ . For an all-occurrences scan, $C$ counts both collisions and genuine matches. If the text and pattern each consist of a repeated single symbol, every window matches and every direct check reads all $m$ symbols. The cost can reach $O(nm)$ .

Randomising the hash parameters can keep the expected number of false candidates small under a suitable collision bound for fixed input. A fixed modulus alone gives no such guarantee. For a deterministic

O(n+m)

bound on a single pattern, Knuth–Morris–Pratt reuses partial matches to avoid rechecking entire candidate windows. Karp and Rabin (1987), Sections 3 and 4

The SelfMadeQuant lesson Hash Tables: Chaining, Open Addressing, and Universal Hashing explains how random selection from a hash family can bound collision probability for fixed input keys. The full lesson requires membership.

Sources

Richard M. Karp and Michael O. Rabin (1987). Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31(2), 249–260.
MIT 6.006 (2011). Recitation 06 on Rabin–Karp and rolling hashes.

Roll the hash forward by one symbol

Two hash hits, one exact match

When the scan is linear

Sources

Related terms

Knuth Morris Pratt algorithm

Sliding window algorithm