Home▸Algorithms & AI▸Rabin–Karp — Rolling Hash String Search

🔍 Rabin–Karp — Rolling Hash String Search

Slide a window across the text, updating a polynomial rolling hash in O(1) per shift, and only compare characters when the window hash matches the pattern hash.

Algorithms & AI2DAdvanced60 FPS

About Rabin–Karp

The Rabin–Karp algorithm, published by Michael O. Rabin and Richard M. Karp in 1987, searches for a pattern of length m inside a text of length n using a polynomial rolling hash instead of comparing characters at every position. The hash of the first window is computed directly, and every subsequent window's hash is derived from the previous one in constant time by subtracting the outgoing character's contribution, shifting the remainder, and adding the incoming character, all under a large prime modulus. Because computing and sliding the hash costs O(1), the algorithm scans the whole text in O(n) time, only falling back to an O(m) character-by-character check when a window's hash matches the pattern's hash — a rare event with a well-chosen modulus, but essential to rule out hash collisions, or "spurious hits". This hashing trick also generalizes elegantly to searching for many patterns simultaneously in a single pass, a task other single-pattern string-matching algorithms handle less efficiently.

Frequently Asked Questions

What is the Rabin–Karp algorithm used for?

Rabin–Karp searches for one or more patterns inside a larger text by comparing hash values instead of raw characters at every position. It is especially well suited to detecting multiple patterns at once (by hashing all of them and checking a rolling text hash against the set) and is a core building block of plagiarism-detection tools and some implementations of the Unix `diff`-family utilities.

Why does a hash match still require character verification?

A hash compresses many possible strings into a fixed-size number, so two genuinely different substrings can occasionally map to the same hash value — a collision. Rabin–Karp treats a hash match only as a candidate and always re-checks the actual characters before confirming a match, which guarantees correctness even though hashing alone cannot.

What is the time complexity of Rabin–Karp?

With a good modulus, the average and typical-case complexity is O(n + m): each of the n − m + 1 window shifts costs O(1) for the hash update, and verification runs only on the rare hash matches. The theoretical worst case is O(n·m), occurring only if adversarial input or a poor modulus causes verification on nearly every window.

How does Rabin–Karp compare to KMP or brute-force search?

Brute-force search re-compares characters from scratch at every position, costing O(n·m) in the worst case. KMP guarantees O(n + m) worst case using a precomputed failure function, but only for a single pattern. Rabin–Karp matches KMP's average speed while extending naturally to searching many patterns simultaneously, which is where it is usually preferred in practice.

⚙ Under the hood

Slide a window across the text, updating a polynomial rolling hash in O(1) per shift, and only compare characters when the window hash matches the pattern hash.

string matchinghashingalgorithmpattern search

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install