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
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More