KMP finds a pattern inside a text by comparing characters
smartly — reusing a precomputed table so no character is re-examined more than a bounded number of
times. Rabin-Karp takes a completely different angle: instead of comparing
characters at all, compare cheap numeric fingerprints of each equal-length window of text
against a fingerprint of the pattern, computed with a rolling hash. Two equal strings always
produce the same fingerprint, so a window whose fingerprint differs from the pattern's can be
ruled out with a single O(1) integer comparison — no character in that window needs
to be looked at. The fingerprint for the next window is derived from the current one in
O(1) too, by rolling one character out and one in, instead of being recomputed from
scratch. The catch, and the reason this page's default example is built the way it is: two
different strings can also produce the same fingerprint. A hash match is a candidate, not
a proof — it still has to be verified character by character before it can be trusted.
Enter a text and a pattern (up to 30 and 12 characters), plus
a modulus for the hash — deliberately small by default (13) so a real
collision shows up in the demo itself, not just in prose. Step through: the pattern's fingerprint
is computed once, then each window's fingerprint is either rolled from the previous one or computed
fresh for the first window. Whenever a window's fingerprint matches the pattern's, the demo
verifies it character by character before counting it as a real match — watch for the window that
matches on hash but fails verification.
The fingerprint is a polynomial hash: treat each character's code point as a digit of a number
in some base, and reduce that number modulo a chosen modulus so it stays
a small, fixed-size integer regardless of string length —
hash(s) = (s[0]·base^(k-1) + s[1]·base^(k-2) + ... + s[k-1]) mod modulus, computed
left to right with Horner's method. What makes it useful for a sliding window is that this
formula rolls: given the hash of text[i..i+m), the hash of text[i+1..i+m+1)
is ((hash − text[i]·base^(m−1))·base + text[i+m]) mod modulus — subtract out the
outgoing character's contribution, shift everything up one place, add the incoming character. Every
term in that update is an O(1) arithmetic operation, so sliding the window one position
costs O(1) regardless of how long the pattern is, instead of the O(m) a
fresh hash computation (or a fresh character-by-character comparison) would cost.
Verification is not optional, and the reason is the pigeonhole principle, not caution for its own
sake: there are infinitely many possible strings of length m but only modulus
possible hash values, so distinct strings sharing a hash isn't a bug to be eliminated, it's
guaranteed to happen for some input. A large modulus (real implementations typically use a
prime near 10^9, sometimes two different hashes checked together) makes a collision
rare for any particular comparison — but "rare" is a probability, not a guarantee, so an algorithm
that skipped verification and trusted the hash alone would be wrong, not just slow, on
the inputs where a collision does land. Verifying turns "probably a match" into "definitely a
match," at the cost of falling back to O(m) character comparisons on exactly the
windows that needed it.
This is the exact scheme the demo above steps through:
function polyHash(str, base, mod) {
let h = 0;
for (let i = 0; i < str.length; i++) h = (h * base + str.charCodeAt(i)) % mod;
return h;
}
function rabinKarpSearch(text, pat, base, mod) {
const n = text.length, m = pat.length;
if (m > n || m === 0) return [];
const patHash = polyHash(pat, base, mod);
let h = 1; // base^(m-1) mod mod, for rolling out the leading char
for (let i = 0; i < m - 1; i++) h = (h * base) % mod;
let windowHash = polyHash(text.slice(0, m), base, mod);
const matches = [];
for (let i = 0; i + m <= n; i++) {
if (i > 0) {
windowHash = (windowHash - (text.charCodeAt(i - 1) * h) % mod + mod * base) % mod;
windowHash = (windowHash * base + text.charCodeAt(i + m - 1)) % mod;
}
if (windowHash === patHash && text.slice(i, i + m) === pat) { // verify — never trust the hash alone
matches.push(i);
}
}
return matches;
}Skipping the character verification "because the hash already matched" is a real bug,
not a theoretical one — the default example above ships one. With modulus 13,
searching "acbcabcacb" for "bca": the pattern's hash is 8.
Window 2 ("bca") and window 5 ("bca") are real matches, hash
8, correctly confirmed. But window 6 ("cac") also hashes to
8 under this modulus — a genuine collision between two different 3-character strings —
and would be silently reported as a third match by a "hash-only" variant that trusts the hash
without comparing characters. Checked directly, not just asserted: running such a variant (identical
to the reference implementation above with the text.slice(i, i + m) === pat check
removed) against this exact input returns [2, 5, 6]; the correct, verified answer is
[2, 5].
A larger modulus makes collisions rarer, not impossible — and a poorly chosen one makes
them common. Try changing the modulus in the demo above from 13 to
1009 and reloading with the same text and pattern: the collision at window
6 disappears (only 2 of the 8 windows now share a hash with the pattern, both real
matches — checked). Go the other direction, down to modulus 2, and it gets much worse:
5 of the 8 windows collide with the pattern's hash, only 2 of which are real, so verification ends
up running on windows across most of the text instead of just the genuine matches. The algorithm's
correctness never depends on the modulus — verification catches every collision regardless —
but its speed does, since every hash collision costs a full O(m) character check.
Rabin-Karp's speed is an average-case argument, not a worst-case guarantee like KMP's.
If hash collisions are rare, the total character-comparison work stays close to the number of real
matches, and the whole search runs in expected O(n + m): O(n) for the
hash comparisons across all windows (each O(1)), plus O(m) per verification
on the (few) windows that need one. But nothing stops every window from colliding — an
unlucky modulus against adversarial or just unlucky input, as the modulus-2 case above
starts to show in miniature — and in that scenario Rabin-Karp verifies every window in full,
degrading to the same O(nm) naive search does no smarter comparisons at all. KMP's
O(n+m) bound holds unconditionally, for every input, because it never depends on a hash
function's behavior; Rabin-Karp's average-case speed is real and usually holds, but it is not the
same kind of guarantee.
Time: O(m) to hash the pattern and the first window, then
O(1) per subsequent window to roll the hash and compare it against the pattern's —
O(n) total for that part, unconditionally. Character verification only runs on windows
whose hash matches; if collisions are rare (the expected case with a well-chosen large prime
modulus) that adds an expected O(m) total, giving expected O(n+m)
overall — but as the Pitfalls section above shows concretely, a bad modulus (or an adversarial
input crafted against a known one) can force verification on every window, degrading to
O(nm) worst case, identical to naive search. Space: O(1)
beyond the input and the list of matches — the rolling hash keeps only the current window's
fingerprint, never a copy of the text or pattern beyond what was already given.
Hashing isn't the only way to skip per-character comparison work: Bitap packs the "which prefixes could be mid-match" state into the bits of a single machine word instead, advancing it with a shift/AND/OR per text character rather than a numeric fingerprint — and unlike a rolling hash, that bit-packed state extends directly to typo-tolerant approximate matching. Boyer-Moore skips work a third way, without hashing or bit-packing at all: compare the pattern right to left instead of left to right, so a single mismatch can rule out several text positions in one step. A fourth way skips comparing the text at all until a pattern is even chosen: Suffix Array sorts the text's own suffixes once, up front, and answers any later pattern with a pair of binary searches instead of a fresh scan. See Choosing an Exact-Match String Matcher for how the fingerprint approach compares to the other nine exact-match entries.