The KMP Algorithm: Fast String Matching Explained

The Knuth-Morris-Pratt (KMP) algorithm finds every occurrence of a pattern string inside a longer text in O(n + m) time, where n is the length of the text and m is the length of the pattern. It does this by never re-examining a character of the text it has already matched — a guarantee the naive approach to string matching can’t make.

Why the naive approach is slow

The obvious way to find a pattern in a text is to try every starting position: slide the pattern along the text one character at a time, and at each position compare it character by character until it either fully matches or a mismatch occurs. In the worst case — a text like "aaaaaaaaab" searched for the pattern "aaab" — this re-checks large overlapping stretches of the text over and over, giving O(n × m) time overall. For long texts and patterns with repetitive structure, that’s a real cost, not just a theoretical one.

The wasted work comes from throwing away information. When a mismatch happens after several characters have already matched, the naive approach forgets everything it just learned and restarts the pattern from its first character at the next position. KMP’s insight is that those already-matched characters tell you exactly how far you can safely skip ahead, without ever needing to re-compare them.

The failure function

KMP’s core idea is a preprocessing step over the pattern alone, producing what’s usually called the failure function (or partial match table). For each position in the pattern, it records the length of the longest proper prefix of the pattern that’s also a suffix of the substring ending at that position.

That sounds abstract, but the intuition is concrete: if you’ve matched the text against the first k characters of the pattern and then hit a mismatch, the failure function tells you the pattern has some prefix that already lines up with a suffix of what you just matched — so instead of restarting the pattern from position 0, you resume comparing from wherever that already-known-good overlap ends. The text pointer never moves backward; only the pattern pointer jumps, using information computed once, up front, from the pattern alone.

Building this table takes O(m) time using a two-pointer scan of the pattern against itself — a cousin of the same idea behind the two-pointers technique used across many string and array algorithms.

The scanning phase

Once the failure function is built, KMP scans the text once, left to right:

1. Compare the current text character against the current pattern character.
2. On a match, advance both pointers.
3. On a mismatch, consult the failure function to decide how far to move the pattern pointer back — never past position 0 — without moving the text pointer backward at all.
4. If the pattern pointer reaches the end of the pattern, a match has been found at the current position; continue scanning for further matches using the same failure-function logic.

Because the text pointer only ever moves forward, each character of the text is examined a bounded number of times regardless of how repetitive the pattern is, which is what gives the algorithm its linear O(n + m) guarantee instead of the naive approach’s quadratic worst case.

Where KMP fits among string-matching approaches

KMP is one member of a family of linear-time string-matching algorithms, each with different tradeoffs. Boyer-Moore skips ahead by scanning the pattern right-to-left and using both a bad-character rule and a good-suffix rule, often outperforming KMP in practice on natural-language text with a large alphabet, though its worst case needs more care to bound. Rabin-Karp instead hashes substrings of the text and compares hashes, which generalizes well to searching for multiple patterns at once. KMP’s advantage is that its worst-case guarantee is simple to prove and it needs no assumptions about the alphabet, which is why it’s the standard example used to teach guaranteed-linear string matching.

The same class of problem shows up in different clothing throughout computer science: a trie solves multi-pattern matching by structuring the patterns themselves rather than preprocessing one at a time, and substring-search ideas resurface in problems solved with the sliding window technique, which also avoids redundant re-scanning by keeping a moving range of already-known state.

Practical relevance

Most languages’ built-in string search (String.prototype.includes, str.find(), and so on) is implemented in native code and often uses algorithms tuned for real-world text rather than KMP specifically — you’re unlikely to hand-implement it for everyday application code. Where KMP still matters directly is in domains that need a hard guarantee against worst-case slowdowns regardless of input: text editors implementing find-and-replace, network intrusion detection systems scanning packet payloads for signatures, and bioinformatics tools searching DNA sequences, where adversarial or highly repetitive input is a realistic concern rather than an edge case. It’s also a staple of algorithm interviews precisely because it forces you to reason about Big O in a case where the naive solution’s inefficiency isn’t obvious until you look for the worst-case input.

The takeaway

KMP achieves linear-time string matching by preprocessing the pattern into a failure function that captures its self-overlaps, then using that table during scanning to skip redundant comparisons without ever moving the text pointer backward. The naive approach re-examines the text on every mismatch; KMP guarantees it never has to. That guarantee is what makes it the standard answer whenever a system needs predictable performance against adversarial or highly repetitive input, even if everyday code usually reaches for a language’s built-in search instead.