Rabin-Karp

Compare numbers instead of strings: hash each window with a rolling hash and only verify on a hash match — O(n+m) average.

9 min read Watch it move Build it

Rabin-Karp flips string matching into *number* matching. It turns the pattern, and every equally-long window of the text, into a number called a hash. Equal strings always hash to the same number, so any window whose hash differs from the pattern's can be skipped instantly — without comparing a single character. The magic that keeps it fast is the rolling hash: each new window's number is computed from the previous one in a single step.

Treat the string as a number

Pick a base d (say the alphabet size) and a prime modulus q. A length-m string is read like a base-d number, taken mod q. For text "31415", base 10, the first 3-char window "314" hashes to 314 mod q; the next window "141" to 141 mod q, and so on. The pattern is hashed the same way, once.

The rolling step

To slide from window "314" to "141" you do not rebuild from scratch. You drop the leading digit, shift left (multiply by the base), and add the new trailing digit — all mod q. With h = d^(m-1) mod q precomputed, the update is a constant-time formula.

// roll the hash one position to the right
// drop text[s], bring in text[s + m]
next = (d * (hash - text[s] * h) + text[s + m]) % q;
if (next < 0) next += q;  // keep it non-negative

1Hash the pattern, and hash the first window of the text.
2Compare the two hashes. If they differ, this window cannot match — slide on.
3If they match, verify character by character (hashes can collide).
4Roll the window's hash to the next position in O(1) and repeat.

A hash match is not a real match

Different strings can share a hash — a hash collision. So every hash match must be confirmed character by character. A bad modulus that collides constantly degrades Rabin-Karp all the way back to O(n·m); a good prime q keeps collisions rare and the average cost linear.

Where it shines

Rabin-Karp generalizes cleanly to searching for many patterns at once (hash them all, look each window's hash up in a set) and to 2-D pattern matching. That flexibility is why it stays useful even though KMP also runs in linear time.

OperationTimeSpace

Average / expected · few spurious hash matchesO(n + m)O(1)

Worst case · every window collides and is verifiedO(n·m)O(1)

Check yourself

After Rabin-Karp finds a window whose hash equals the pattern's hash, why must it still compare the characters?