Rabin–Karp — Rolling Hash String Search

#️⃣ Rabin–Karp

Rolling hash string search

Window start 0 / 0

Matches found: 0

Setup

Text

Pattern

Small modulus (demo collisions)

Controls

Stats

Window start

Window hash

Pattern hash

Comparisons

Match log

Info & Theory

Rabin–Karp finds occurrences of a pattern of length m inside a text of length n by sliding a window of size m across the text and comparing a numeric fingerprint — a hash — of the window against the hash of the pattern, instead of comparing characters directly at every position.

The polynomial rolling hash

Each window of characters c₀ c₁ … c(m−1) is treated as digits of a number in base b:

h = (c₀·b^(m−1) + c₁·b^(m−2) + … + c(m−1)) mod p
b is a base (e.g. 256), p a large prime (e.g. 1,000,000,007) that keeps the hash bounded and reduces collisions.

Sliding in O(1)

Recomputing the hash from scratch at every position would cost O(m) per shift. Instead, Rabin–Karp updates it incrementally: remove the contribution of the outgoing character, shift the remaining digits up one place, and add the incoming character — h′ = ((h − text[i]·b^(m−1))·b + text[i+m]) mod p, adding p before the final mod whenever the subtraction goes negative. This costs O(1) per shift regardless of m.

Why verify after a hash match

Different windows can occasionally collide to the same hash value even though their characters differ — a spurious hit. Whenever the window hash equals the pattern hash, Rabin–Karp performs an explicit character-by-character comparison to confirm a true match before reporting it, guaranteeing correctness regardless of collisions.

Complexity

Average and typical-case running time is O(n + m), since verification is only triggered on (rare) hash matches. Worst case is O(n·m) if many spurious hits force repeated full verifications — extremely unlikely with a large prime modulus, but demonstrable here with the small-modulus option. Rabin–Karp's hashing idea also extends naturally to searching for multiple patterns at once in a single pass, which single-pattern algorithms cannot do as cheaply.

About Rabin–Karp

Last updated: 11 July 2026

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.