KMP Algorithm
Linear-time string matching algorithm
The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm that finds all occurrences of a pattern within a text in linear time by avoiding redundant character comparisons using a precomputed failure function.
Definition
The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm that finds all occurrences of a pattern within a text in linear time by avoiding redundant character comparisons using a precomputed failure function.
Overview
Naive string matching compares a pattern against every possible starting position in the text, which can require re-examining already-matched characters after a mismatch, leading to O(n*m) worst-case time. KMP avoids this inefficiency by precomputing, for the pattern itself, a "failure function" (also called the partial match or prefix table) that records, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix of that prefix. This table encodes exactly how far the pattern can be shifted after a mismatch without missing any potential match, so the algorithm never needs to re-scan characters in the text it has already examined. The result is that KMP performs pattern matching in O(n + m) time overall — O(m) to build the failure function and O(n) to scan the text — a guaranteed linear bound regardless of the pattern's or text's structure, unlike some other algorithms whose worst case can degrade under adversarial input. This predictability made KMP, published by Knuth, Morris, and Pratt in 1977 (with Morris having devised it independently somewhat earlier), a foundational result in the study of string algorithms and a common addition to any programming language's or library's string-search toolkit alongside simpler substring functions. KMP is widely taught as the canonical introduction to linear-time string matching and remains relevant in text editors and command-line tools' search functionality, DNA and protein sequence pattern searches in bioinformatics where exact substring occurrences must be located quickly, and network intrusion detection systems that scan packet payloads for known attack signatures. Its failure-function technique also generalizes to other problems, including certain string-periodicity detection algorithms and as a building block within more advanced multi-pattern matching algorithms like Aho-Corasick.
Key Concepts
- Finds all occurrences of a pattern in a text in O(n + m) linear time
- Precomputes a failure function encoding safe shift distances after mismatches
- Never re-examines already-matched text characters
- Guarantees linear-time performance regardless of input structure
- Published by Knuth, Morris, and Pratt in 1977
- Common alternative or complement to naive substring search
- Failure-function technique generalizes to string periodicity detection
- Building block for multi-pattern algorithms like Aho-Corasick