String Pattern Matching: Naive, KMP, and Rabin-Karp
Concept
Finding every occurrence of a pattern of length m inside a text of length n is a problem every engineer has used (str.find, a log grep, a text editor's search) without necessarily knowing which algorithm answers it underneath. The naive approach — slide the pattern across the text one position at a time, comparing character by character and restarting the comparison from scratch on a mismatch — costs O(nm) in the worst case, because a pathological input (e.g., searching for "aaaab" inside "aaaaaaaaaa...") forces nearly a full re-comparison at every position. Two classic algorithms both bring this down to O(n + m), but by attacking the problem from opposite directions.
Knuth-Morris-Pratt (KMP) exploits information the naive approach throws away: when a mismatch happens partway through a comparison, the characters already matched tell you something about the pattern's own internal structure, and that's enough to know the next possible match position without re-scanning text you've already looked at. KMP precomputes a "failure function" (also called the partial-match table) over the pattern itself — for each prefix of the pattern, how long is the longest proper prefix that is also a suffix — and uses it to skip forward on a mismatch instead of restarting. The text pointer never moves backward, which is what gives the O(n) bound over the text regardless of how the pattern is structured.
Rabin-Karp takes an entirely different approach: instead of comparing characters, it compares hashes of the pattern and of each length-m window of the text, using a rolling hash that can be updated in O(1) from one window to the next (add the incoming character's contribution, subtract the outgoing one) rather than recomputed from scratch. A hash match is a candidate — an actual character comparison still confirms it, to rule out hash collisions — but on non-matching windows, the O(1) hash comparison usually rejects the position immediately without ever touching the pattern's characters. Its real strength shows up in multi-pattern search: hashing k patterns once and checking each text window's hash against a set is close to O(n) total regardless of k, whereas running k independent KMP passes costs O(k·n).
Tradeoffs
| Algorithm | Time (typical) | Time (worst case) | Space | Best fit |
|---|---|---|---|---|
| Naive | O(n) | O(nm) | O(1) | Short patterns, one-off searches where simplicity beats speed |
| KMP | O(n + m) | O(n + m) — guaranteed | O(m) for the failure table | Single-pattern exact match where a hard worst-case guarantee matters |
| Rabin-Karp | O(n + m) | O(nm) if hash collisions are frequent (rare with a good hash) | O(1) beyond the rolling hash | Multi-pattern search (plagiarism/DNA-sequence scanning), or when hashing rather than character comparison is the cheaper primitive |
KMP's worst case is a hard guarantee, independent of the hash function — Rabin-Karp's O(n+m) is an expected bound that degrades toward O(nm) if the hash function collides often on the given alphabet, which is a real (if rare, with a well-chosen modulus/base) risk an implementer has to actually verify rather than assume away.
Walked-through scenario
Searching for the pattern "ABABC" in the text "ABABABC":
Naive: at text position 0, compares A-A, B-B, A-A, B-B, A(pattern)-B(text) — mismatch at the 5th character, discard all 4 matched characters, restart the whole comparison at text position 1. It has no memory that "ABAB" was already confirmed to match.
KMP: precomputes the failure table for "ABABC" first. The key insight lives at that same mismatch point: the 4 characters already matched ("ABAB") have a known internal structure — its longest proper prefix that's also a suffix is "AB" (length 2). So instead of restarting at text position 1, KMP resumes the comparison already knowing the first two characters ("AB") match, and only needs to compare the pattern's 3rd character against the text's next position — skipping re-comparison of text KMP has effectively already "seen." Over the whole text, the text pointer only ever moves forward, giving the O(n) bound.
Rabin-Karp: instead of character comparisons, computes a rolling hash of "ABABC" (the pattern) once, then hashes each 5-character window of the text ("ABABA", "BABAB", "ABABC", ...) using the rolling update. Most windows' hashes won't match the pattern's hash and get rejected in O(1); the one window that does hash-match ("ABABC" itself) gets a final character-by-character confirmation to rule out a collision.
Common pitfall
Reaching for Rabin-Karp's rolling hash without picking the modulus and base carefully, or skipping the confirming character comparison on a hash match "because the hash probably means they're equal" — both turn the algorithm's expected O(n+m) into either wrong results (false-positive matches on a real collision) or a degraded O(nm) if collisions cluster. Equally common: reaching for KMP or Rabin-Karp at all for a single short, one-off search where the naive approach's simplicity and effectively-linear real-world performance (worst-case pathological inputs are rare in practice) make the added complexity not worth it.
Engineering Lens
The naive-vs-KMP-vs-Rabin-Karp progression is a clean instance of a recurring pattern-matching move: convert wasted repeated work into precomputed or incrementally-updated state. KMP precomputes structure in the pattern so the text scan never backtracks; Rabin-Karp precomputes a hash of the pattern and maintains a rolling hash of the text window so most positions are rejected in O(1) without ever touching the pattern's characters. Neither trick is specific to text — the same "don't redo work you already have information about" instinct underlies suffix automata, tries for prefix search, and even cache-invalidation strategies elsewhere in this vault. In production, the actual engineering decision is rarely "hand-implement KMP" — it's knowing that a language's built-in substring search or grep/ripgrep already uses a variant of these ideas (or the even faster Boyer-Moore, which skips using information from the text side), and reaching for Rabin-Karp specifically only when the real requirement is multi-pattern search (e.g., scanning a document against a large blocklist of substrings in one pass) rather than a single needle in a haystack.
Sources
- String Matching Algorithms. Knuth-Morris Pratt and Rabin-Karp — Medium
- Knuth–Morris–Pratt algorithm — Wikipedia
- Rabin–Karp algorithm — Wikipedia