Rabin-Karp vs KMP
Use KMP when you need a guaranteed O(n + m) single-pattern search with no chance of a bad case. Use Rabin-Karp when you are searching for many patterns at once, or comparing substrings repeatedly, where one rolling hash serves every comparison.
Both beat the naive O(nm) scan, and they do it in different currencies. KMP spends a preprocessing pass on the pattern to learn how far it can safely jump after a mismatch, and never backs up in the text. Rabin-Karp turns each window into a number it can update in O(1) as the window slides, so comparing a window to the pattern is comparing two integers.
Side by side
| Dimension | Rabin-Karp | KMP |
|---|---|---|
| Worst case | O(nm) if every hash collides | O(n + m), guaranteed |
| Average case | O(n + m) | O(n + m) |
| Preprocessing | Hash the pattern, O(m) | Build the failure table, O(m) |
| Extra space | O(1) | O(m) for the table |
| Many patterns | Natural, hash them into a set | One table per pattern |
| What can go wrong | Collisions, needing a verification compare | Nothing, but the table is fiddly to derive |
When to pick each
Rabin-Karp
- Searching for a set of patterns of the same length, where every window is hashed once and checked against a set.
- Repeated substring comparisons, as in finding the longest repeated substring, where prefix hashes answer each comparison in O(1).
- Detecting duplicate blocks or plagiarism, where approximate matching on hashes is the point.
KMP
- A single pattern with a hard worst-case requirement, where collisions are not acceptable.
- Streaming text that you cannot rewind, since KMP never moves backwards in the input.
- An interview that asks about the failure function, which is the part being tested.
Treating a hash match as a match. Two different windows can hash to the same number, so Rabin-Karp has to compare the characters once the hashes agree, and skipping that verification gives wrong answers on adversarial input. The other trap is a weak modulus: a small prime makes collisions common enough to degrade the average case, and a power of two is worse, since it throws away the high bits.
Questions people ask
What exactly does KMP precompute?
For each position in the pattern, the length of the longest proper prefix that is also a suffix of the part matched so far. On a mismatch, that number says how far the pattern can shift without missing a possible match, so the text pointer never retreats. Deriving the table is the harder half of the algorithm, and it is what interviewers probe.
How does the rolling hash update in O(1)?
By treating the window as a number in some base. Sliding one position means subtracting the leaving character times the base to the power of the window length, multiplying by the base, and adding the arriving character, all modulo a large prime. Three arithmetic operations, independent of the window size.
Is Java's indexOf one of these?
No. String.indexOf is the naive nested scan with some tuning, which is O(nm) in the worst case and fine in practice because real text mismatches early. The specialised algorithms matter when the input is adversarial or when the same text is searched many times, which is exactly when interviewers ask.