KMP is fast for one pattern but searching for 1,000 patterns in the same text means 1,000 passes through it. Rabin-Karp takes a different approach: hash each window of the text and compare the hash to the pattern's hash. Equal hashes trigger a character-by-character verification; unequal hashes are skipped in O(1). With a rolling hash, the hash of each new window is computed from the previous one in O(1).

This chapter covers the rolling hash, modular arithmetic, the full algorithm, collision handling, and multi-pattern search.

The strategy:

Comparing two numbers is O(1); comparing two strings of length m is O(m). A good hash function makes most windows differ from the pattern in their hash value, so the O(m) verification fires rarely.

Two different strings can produce the same hash, a collision. When the hashes match but the strings do not, that is a spurious hit. Verification handles them. With a good hash function, spurious hits are rare.

Computing each window's hash independently is O(m) per window and O(n*m) overall, the same as brute force. A rolling hash computes the next window's hash from the current one in O(1), because consecutive windows differ by exactly two characters: one leaves the left edge, one enters the right.

Polynomial Hash Function

Each character's contribution depends on its position:

Here d is the base (often the alphabet size, like 256 for ASCII), and s[i] is the numeric value of the character (ASCII code).

The polynomial form is better than a simple sum of character values because it makes the hash sensitive to position: "ABC" and "CBA" sum to the same value but have different polynomial hashes. It is also what makes the O(1) rolling update work.

Example with d = 256 and pattern "ABC":

The Rolling Update

Sliding the window one position right removes the leftmost character and adds a new rightmost character:

Step by step:

Analogous to a sliding window sum, but with a polynomial instead of a plain sum.

The polynomial values grow quickly. With d = 256 and m = 20, the leading term is 256^19, a 46-digit number that no primitive integer holds.

Fix: pick a large prime q (commonly 10^9 + 7 or 10^9 + 9) and do every hash operation modulo q:

The rolling update becomes:

Two details to get right:

1. Pre-compute d^(m-1) mod q

Compute it once before the main loop using modular exponentiation.

2. Handle negative remainders

Subtracting s[i] * d^(m-1) can make the intermediate value negative. In C, C++, Java, JavaScript, and most languages, % of a negative number returns a negative result. Fix:

This keeps the hash in [0, q-1]. Python's % already returns a non-negative result for a positive divisor, so the correction is a no-op there.

Skipping this correction is a common Rabin-Karp bug. If the hash goes negative, the algorithm reports wrong matches without crashing.

Two phases: preprocessing (compute pattern hash and first window hash) and searching (slide the window, comparing hashes).

Full implementation:

Preprocessing:

Compute h = d^(m-1) mod q = 256^3 mod 101.

Pattern hash for "ABCD":

First window hash ("ABCC"):

Searching:

One character-by-character verification out of six windows. The other five were ruled out by hash comparison alone.

No spurious hits in this example. With a small modulus like 101, spurious hits are more likely. In practice, q = 10^9 + 7 makes the chance of a spurious hit at any window roughly 1 in a billion.

A spurious hit is a window whose hash matches the pattern's hash but whose characters differ. Different strings can land on the same hash because the hash function maps a large space (all strings of length m) to a smaller one (integers from 0 to q-1).

For a single window, the probability of a spurious hit is about 1/q. Across n - m + 1 windows, the expected number is (n - m + 1) / q. With q = 10^9 + 7 and a text of length 10^6, that is fewer than 0.001 spurious hits on average.

The worst case for Rabin-Karp comes from one of two situations:

The "AAAA...A" text with "AAA...AB" pattern is sometimes cited as a worst case but is not: those two strings differ in their last character, so their polynomial hashes are typically different and verification rarely fires.

Mitigating Collisions

Rabin-Karp's O(n+m) is expected, not guaranteed. KMP's O(n+m) is guaranteed regardless of input. The trade-off is worth taking when the multi-pattern capability matters.

Double Hashing in Practice

A single hash with q = 10^9 + 7 gives a collision probability of about 10^-9 per window. Double hashing drives that to about 10^-18, low enough that many implementations skip the character-by-character verification entirely and trust the double hash. The cost is one extra multiply and modulo per window.

For safety-critical code (cryptographic tools, plagiarism detection where false positives matter), keep the character verification even with double hashing. For typical competitive-programming or batch-processing use cases, skipping it is fine.

Multi-pattern is where Rabin-Karp beats KMP. Searching for k patterns with KMP means k passes over the text, O(n*k). Rabin-Karp scans for all k patterns in a single pass.

Approach:

Assuming all k patterns have the same length m, total time is O(n + km): O(km) to hash the patterns, then O(n) to scan the text.

For patterns of different lengths, group them by length and run one pass per distinct length. Aho-Corasick is the standard algorithm when you have many patterns of varying lengths and need the lowest possible asymptotic cost; it runs in O(n + total pattern length + number of matches) in a single pass.

Real-world workloads that use multi-pattern hashing:

KMP preprocesses the pattern into a failure function and avoids redundant character comparisons. Rabin-Karp preprocesses the pattern into a hash value and enables O(1) window comparisons.

KMP when worst-case time matters: a single pattern, possibly adversarial input.

Rabin-Karp when searching many patterns at once, or when the rolling hash is useful for related problems (longest duplicate substring, content-defined chunking, similarity hashing).

Time Complexity:

Space Complexity:

Comparison with brute force:

Expected O(n + m) makes Rabin-Karp competitive with KMP for single patterns and better for multi-pattern search. The O(n * m) worst case is a theoretical concern that rarely shows up in practice with a good hash function and large prime.