The idea: compare hashes first, characters only on a hit
To find a pattern P of length m in a text T of length n, the naive method compares P with every window T[s..s+m−1] character by character. Rabin-Karp (1987) first compares a number: the hash of the window against the hash of the pattern. Different hashes prove the strings differ, so the window is skipped without reading a character. Equal hashes only make the window a candidate, a hash hit, which is then checked character by character.
On this page the alphabet is the ten digits and the base is d = 10, as in CLRS, so a window's value is the number you read (41815) and its hash is that number mod q. Real implementations use the byte or character code as the digit and base 256 or a larger number; nothing else changes.
The rolling update
Hashing every window from scratch costs m operations per window, no better than the naive check. The trick is that neighbouring windows share m − 1 digits. Going from window s to s + 1 drops the leading digit and adds one on the right:
h = d^(m−1) mod q (weight of the leading digit, computed once) t(s+1) = ( d · ( t(s) − T[s]·h ) + T[s+m] ) mod q
All arithmetic is done mod q, so the numbers never grow past about d·q. The subtraction can go below zero (7 − 12 = −5 above); in C or Java the % operator keeps the sign, so add q before going on. The pattern hash p and the first window hash t(0) are the only values computed digit by digit (Horner's rule: v = (v·d + digit) mod q). (Demo: one shift at a time.)
Spurious hits and verification
A hash squeezes a 5-digit number into q values, so different windows must share hashes. Equal hashes with different strings are a spurious hit (a false positive). Rabin-Karp never reports a match on the hash alone: on every hit it compares P[j] with T[s+j] until a mismatch or the end. That makes the answer always correct; the hash only decides how much work is done. A miss is never wrong: different hashes always mean different strings. (Demo: whole search, q = 13: the very first window, 41815, is a spurious hit, rejected after one character.)
Choosing the modulus
With a "random" hash each window collides with the pattern with probability about 1/q, so a large prime q makes spurious hits rare. A badly chosen q throws away information about the window, and many windows collide. On the text of the demos:
| q | what the hash keeps | spurious hits | character compares |
|---|---|---|---|
| 997 (large prime) | the number mod 997 | 0 | 5 |
| 13 (prime) | the number mod 13 | 1 (41815) | 6 |
| 10 (= the base) | only the last digit: h = 104 mod 10 = 0 | 3 (every window ending in 5) | 8 |
| 9 (= base − 1) | the digit sum mod 9: h = 1 | 3 (15314, 53141, 15431: anagrams of 31415) | 8 |
A modulus that shares factors with the base (10 = 2·5) or divides dk − 1 (9 divides 10 − 1) gives the hash a structure that real text can hit again and again. That is why q is a prime that does not divide the base, typically near 109 (such as 109 + 7) so that d·q still fits in a 64-bit integer. Choosing q (or the base) at random when the program starts also protects against inputs crafted to collide. (Demos: q = 997, q = 10, q = 9.)
Cost
Precomputing h, p and t(0) takes O(m). Then each of the n − m + 1 windows costs one hash compare and one O(1) roll, plus m character compares at most on a hit. With few hits the total is O(n + m) expected. In the worst case every window is a hit and the verification costs O(n·m), the same as the naive method. That happens when the pattern really occurs everywhere (Demo: worst case: 15 matches, 75 character compares) or when the modulus is bad.
For a single pattern, KMP or Boyer-Moore is usually faster in practice. Rabin-Karp shines where a hash of a sliding window is what you need: searching for many patterns of the same length at once (hash them all into a set and look up each window hash), finding repeated substrings and plagiarism (fingerprints), two-dimensional search, and rolling checksums such as the one rsync uses to find matching blocks. See String Search Race to watch Rabin-Karp run against naive search, KMP, Boyer-Moore and Horspool on the same text, and Closed Hashing for collisions in a hash table.
What the page leaves out
Character alphabets and base 256 (the page uses digits so the arithmetic is readable); hashing with two moduli at once to make collisions rarer still; the Monte Carlo version that skips the character check and accepts a tiny chance of a wrong answer; polynomial rolling hashes used for comparing substrings in O(1) after O(n) preprocessing; Rabin fingerprints over GF(2) and content-defined chunking; and the multi-pattern and 2-D variants mentioned above.