Rabin-Karp
Turn the pattern into a number, its hash, and do the same for each window of the text. Different hashes prove a window is not a match, without reading its letters. Sliding the window one step updates its hash in constant time: take the outgoing letter out, bring the incoming one in.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| text | a | b | c | a | b | c | a | b | c |
| hash |
Find "cab" in "abcabcabc" by comparing number fingerprints of each window, and only checking letters when the fingerprints agree.
1const code = (s, k) => s.charCodeAt(k) - 96; // a = 1, b = 2, ...23function rabinKarp(text, pat, base = 31, mod = 13) {4 const m = pat.length;5 let ph = 0, th = 0, high = 1;6 for (let k = 0; k < m - 1; k++) high = (high * base) % mod;7 for (let k = 0; k < m; k++) {8 ph = (ph * base + code(pat, k)) % mod;9 th = (th * base + code(text, k)) % mod;10 }11 const hits = [];12 for (let i = 0; i + m <= text.length; i++) {13 if (ph === th && text.slice(i, i + m) === pat) hits.push(i);14 if (i + m < text.length) {15 th = ((th - code(text, i) * high) * base + code(text, i + m)) % mod;16 if (th < 0) th += mod;17 }18 }19 return hits;20}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n + m | few hash matches, so few letter checks |
| average | n + m | with a large modulus, collisions are rare |
| worst | n · m | every window collides and needs a full letter check |
| space | 1 | a few numbers for the hashes |
Where it breaks
- Equal hashes do not prove a match. Pick Collisions: two windows besides "cat" share its hash. That is why the letters are always checked when hashes agree. The modulus here is 13, tiny on purpose; real code uses a large prime and collisions become rare.
- Negative remainders. Removing the outgoing letter can push the hash below zero. In JavaScript
%keeps the sign, so the code adds the modulus back. Python's%never returns a negative here. - Where it shines. Hashes compare in one step whatever their length, so Rabin-Karp can look for many patterns at once, or find repeated chunks across files, as plagiarism checkers do.