The Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt (KMP) algorithm^[1] is a foundational exact string matching algorithm in computer science.^[25] It solves the problem of finding all occurrences of a specific pattern string within a larger text string.^[26] Unlike naive approaches that re-evaluate previously matched characters after a mismatch, KMP achieves linear time complexity by utilizing the internal structure of the pattern itself. It precomputes a partial match table that dictates how far the pattern can be shifted without missing potential matches, thereby avoiding redundant character comparisons.^[27]

Operating in $O(n + m)$ time, where $n$ is the length of the text and $m$ is the length of the pattern, KMP guarantees optimal worst-case performance for single-pattern search. The algorithm requires $O(m)$ auxiliary space to store the precomputed table. This efficiency makes it highly suitable for processing continuous data streams, as it never needs to backtrack through the text string.

First published jointly in 1977^[2], the algorithm represents a classic example of theoretical computer science yielding a highly practical tool.^[28] Its development bridged abstract automata theory and applied software engineering, establishing a baseline for subsequent research in string processing^[3], computational biology, and data retrieval.

The String Matching Problem

The exact string matching problem is formalized mathematically using alphabets and sequences. Let $\Sigma$ be a finite set of symbols, called an alphabet. A string $S$ of length $n$ is a sequence of symbols $S[0]S[1]\dots S[n-1]$ where each $S[i] \in \Sigma$. A string $w$ is a substring of $S$ if there exist strings $u$ and $v$ such that $S = uwv$. If $u$ is the empty string, $w$ is a prefix of $S$. If $v$ is the empty string, $w$ is a suffix of $S$. Given a text array $T$ of length $n$ and a pattern array $P$ of length $m$, the objective is to find all valid starting indices $s$ (where $0 \le s \le n - m$) such that the substring $T[s \dots s + m - 1]$ is identical to $P[0 \dots m - 1]$.

The most straightforward approach to this problem is the naive, or brute-force, algorithm. The naive algorithm aligns the pattern at the beginning of the text and compares characters sequentially. If a mismatch occurs at any position, the algorithm shifts the pattern exactly one position to the right and restarts the comparison from the first character of the pattern. While easy to implement, this approach suffers from severe performance degradation in specific cases. Consider a worst-case scenario where the text consists of a long sequence of identical characters followed by a different character, such as $T = \text{"AAAAAAAAAAAAAAB"}$, and the pattern has a similar structure, such as $P = \text{"AAAAAAB"}$. The naive algorithm will successfully match the first six 'A' characters, fail at the 'B', shift the pattern by one position, and then re-evaluate the same 'A' characters. For a text of length $n$ and a pattern of length $m$, this results in exactly $(n - m + 1) \times m$ comparisons in the worst case, yielding a quadratic time complexity of $O(n \times m)$.

A secondary issue with the naive algorithm is its reliance on backtracking. When a mismatch occurs, the text pointer must move backward to the character immediately following the start of the current attempted match. If the text is being read from a non-seekable input source, such as a network socket or a sequential file stream, backtracking requires the system to buffer previously read characters. This buffering increases memory overhead and complicates the implementation. The Knuth-Morris-Pratt algorithm was designed specifically to eliminate both the $O(n \times m)$ worst-case time complexity and the need for text backtracking.

Discovery and History

The formulation of the KMP algorithm is a well-documented instance of independent co-discovery.^[28] The algorithm was conceptualized in 1970 and formally published in the SIAM Journal on Computing by Donald E. Knuth, James H. Morris, and Vaughan R. Pratt.

Donald Knuth's path to the algorithm originated in automata theory. In 1971, Stephen Cook published a theorem^[4] demonstrating that a two-way deterministic pushdown automaton could be simulated in linear time on a random-access machine. A two-way deterministic pushdown automaton features a read-only input tape that can move left and right, alongside a memory stack. Knuth attended a symposium^[5] where Cook presented this research. Knuth realized that the string-matching process could be modeled as exactly this type of automaton. By manually tracing Cook's simulation for the specific case of pattern matching, Knuth extracted a linear-time algorithm. However, his initial formulation had a running time that depended on the size of the alphabet $\Sigma$. Vaughan Pratt, who was collaborating with Knuth at Stanford University, refined the data structures to make the running time independent of the alphabet size, achieving the strict $O(n + m)$ bound.

Concurrently, James H. Morris was working on a practical engineering problem at the University of California, Berkeley. Morris was tasked with developing a text editor for the CDC 6400, a mainframe computer used extensively in scientific computing. The operating system of the CDC 6400 handled file input and output using a buffering scheme that made reading forward highly efficient but reading backward computationally prohibitive. If a user searched for a string and the editor used the naive algorithm, a mismatch would require the system to rewind the file pointer, triggering expensive disk operations. Morris independently invented the failure function to allow the editor to process the file stream sequentially, completely unaware of the theoretical work being done by Knuth and Pratt. When Knuth learned of Morris's practical implementation, the three researchers combined their findings into a single comprehensive paper.

Prior art also exists outside the United States. In 1969, Yuri Matiyasevich independently discovered^[6] a similar linear-time string-matching algorithm. Matiyasevich approached the problem from the perspective of computability theory. He utilized a specific model of a two-dimensional Turing machine to process strings over a binary alphabet, aiming to prove that the inclusion relation could be recognized in real-time. Due to the geopolitical barriers of the Cold War and the specific theoretical framing of his paper, Matiyasevich's contribution was not widely recognized in Western computer science literature until years later.

Mechanism and Operation

The KMP algorithm avoids redundant comparisons by answering a specific question. When a mismatch occurs, how much of the pattern's prefix has already been matched, and does that prefix contain a smaller prefix that is also a suffix? By analyzing the pattern's internal symmetry, the algorithm determines the maximum safe shift.

The Prefix Function

The core of KMP is the preprocessing phase, which constructs an array of integers known as the failure function or the partial match table. In modern literature, this is frequently called the lps array, standing for "Longest Proper Prefix which is also Suffix". For a pattern $P$ of length $m$, the table is an array of length $m$. Each entry lps[i] stores the length of the longest proper prefix of the substring $P[0 \dots i]$ that is identical to a suffix of $P[0 \dots i]$. A proper prefix is a prefix that is strictly shorter than the string itself.

Consider the pattern $P = \text{"ABABCABAB"}$. The lps array is computed as follows:

• lps[0] = 0: The substring is "A". There is no proper prefix.
• lps[1] = 0: The substring is "AB". The only proper prefix is "A", and the suffix is "B". They do not match.
• lps[2] = 1: The substring is "ABA". The proper prefixes are "A" and "AB". The suffixes are "A" and "BA". The longest match is "A", which has a length of 1.
• lps[3] = 2: The substring is "ABAB". The longest matching prefix and suffix is "AB", length 2.
• lps[4] = 0: The substring is "ABABC". No proper prefix matches a suffix.
• lps[5] = 1: The substring is "ABABCA". The longest match is "A", length 1.
• lps[6] = 2: The substring is "ABABCAB". The longest match is "AB", length 2.
• lps[7] = 3: The substring is "ABABCABA". The longest match is "ABA", length 3.
• lps[8] = 4: The substring is "ABABCABAB". The longest match is "ABAB", length 4.

The table is built in $O(m)$ time using a dynamic programming approach^[7]. The algorithm maintains a length variable representing the length of the current longest prefix suffix. It iterates through the pattern starting from the second character. If the current character matches the character at the length index, length is incremented. If there is a mismatch, the algorithm does not reset length to zero immediately. Instead, it falls back to lps[length - 1] to find a shorter prefix that might still match the current suffix. This recursive fallback is the mathematical heart of the algorithm.

The Search Phase

During the search phase, the algorithm maintains two pointers: $i$ for the text $T$ and $j$ for the pattern $P$. Both pointers start at 0. The characters $T[i]$ and $P[j]$ are compared sequentially.

• If $T[i] == P[j]$, both $i$ and $j$ are incremented.
• If $j$ reaches $m$, a complete match is found at text index $i - j$. The pointer $j$ is then updated to lps[j - 1] to continue searching for overlapping matches.
• If a mismatch occurs ($T[i] \neq P[j]$):
  • If $j > 0$, the algorithm updates $j = lps[j - 1]$. The text pointer $i$ is not changed. This operation shifts the pattern to the right, aligning the longest known matching prefix with the corresponding suffix in the text that was just read.
  • If $j == 0$, the algorithm simply increments $i$ to check the next character in the text.

The mathematical safety of this shift is absolute. Suppose a mismatch occurs at $P[j]$ and $T[i]$. The algorithm has already established that $P[0 \dots j-1]$ perfectly matches $T[i-j \dots i-1]$. To find the smallest valid shift $k > 0$, the prefix of the shifted pattern must match the suffix of the already matched text. Since the matched text is identical to $P[0 \dots j-1]$, this is equivalent to finding the longest proper prefix of $P[0 \dots j-1]$ that is also a suffix of $P[0 \dots j-1]$. This is exactly the value stored in lps[j-1]. Any smaller shift would align a prefix and suffix that are known to be unequal, guaranteeing a mismatch. Thus, KMP safely bypasses impossible alignments.

Pseudocode

The following pseudocode demonstrates both the preprocessing and search phases in a single unified structure.

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    if m == 0:
        return []

    # Preprocessing: Compute the LPS array
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    # Search phase
    matches = []
    i = 0  # index for text
    j = 0  # index for pattern
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            matches.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return matches

Complexity Analysis

The space complexity of the algorithm is strictly $O(m)$ to store the lps array. The time complexity for building the table is $O(m)$. The search phase takes $O(n)$ time.

The $O(n)$ time bound for the search phase is proven using amortized analysis^[8]. Although there is a conditional fallback mechanism when a mismatch occurs (which can decrease $j$ multiple times for a single $i$), the total number of character comparisons is strictly bounded.^[29] This can be demonstrated using the potential method. Let the potential function $\Phi$ be the value of the pattern pointer $j$. When the characters match ($T[i] == P[j]$), both $i$ and $j$ are incremented. The actual cost of this operation is 1 comparison, and the potential $\Phi$ increases by 1. The amortized cost is the actual cost plus the change in potential, which equals 2. When a mismatch occurs, the algorithm updates $j = lps[j - 1]$. The actual cost is 1 comparison, but the potential $\Phi$ strictly decreases because $lps[j - 1] < j$. The decrease in potential offsets the actual cost of the fallback operation. Because the potential $\Phi$ starts at 0, never becomes negative, and increases at most $n$ times, the total actual cost of all operations over the entire search cannot exceed the total amortized cost, which is bounded by $2n$. The overall time complexity is therefore $O(n + m)$. Formal verification of these bounds, including the mathematical proof of correctness^[9], relies on establishing loop invariants that guarantee the longest matching prefix is never skipped.

Important Variants

Real-Time KMP and Deterministic Finite Automata

The standard KMP algorithm is not strictly "real-time" because a single text character might trigger multiple fallback operations in the lps array, causing a temporary delay.^[30] To achieve strict real-time processing, where the time spent on each text character is bounded by a constant $O(1)$, the algorithm can be modeled as a full Deterministic Finite Automaton (DFA)^[10].

In this variant, a complete state transition table of size $O(m \times |\Sigma|)$ is constructed. The states represent the number of matched characters. For any given state and any given input character, the table provides the exact next state in a single lookup, completely eliminating the while loop fallback mechanism. While this guarantees constant processing time per character, the $O(m \times |\Sigma|)$ space requirement makes it impractical for large alphabets, such as Unicode.

Simon's Algorithm

To resolve the space inefficiency of the DFA approach, Imre Simon introduced an algorithm^[11] in 1993 that achieves real-time performance while requiring only $O(m)$ space. Simon's algorithm uses a more economical representation of the automaton. Instead of storing every possible transition for every character, it stores only the significant transitions (those that do not lead back to the initial state) and computes the remaining transitions on the fly without the cascading delays characteristic of the standard KMP fallback.

Apostolico-Crochemore Algorithm

The Apostolico-Crochemore algorithm^[12], published in 1991, builds upon KMP by incorporating a different preprocessing strategy to reduce the total number of character comparisons. While standard KMP guarantees at most $2n - 1$ comparisons, Apostolico-Crochemore reduces this upper bound to $\frac{3}{2}n$ comparisons. It achieves this by computing the period of the pattern and exploiting this periodicity to avoid re-comparing characters that are mathematically guaranteed to match. This variant is highly effective when the pattern contains repetitive sub-patterns.

Crochemore's Ordered Alphabet Algorithm

Another notable variant is the algorithm for String-Matching on Ordered Alphabets^[13] developed by Maxime Crochemore in 1992. While KMP requires $O(m)$ auxiliary space to store the lps array, Crochemore's algorithm achieves the same $O(n + m)$ linear time complexity using only $O(1)$ auxiliary space (a fixed number of memory locations), provided the alphabet is ordered. It does this by computing the maximal suffixes of the pattern on the fly, effectively combining the linear-time guarantees of KMP with the constant-space footprint of the naive algorithm.

Two-Way String Matching

In 1991, Maxime Crochemore and Dominique Perrin published the Two-Way string-matching algorithm^[14]. This variant combines the forward-scanning logic of KMP with the backward-scanning heuristics of the Boyer-Moore algorithm. The Two-Way algorithm factors the pattern into two halves based on its critical factorization. It first compares the right half of the pattern from left to right. If that half matches, it compares the left half from right to left. Like KMP, it guarantees linear $O(n + m)$ worst-case time complexity. However, unlike KMP, which requires $O(m)$ auxiliary space for the lps array, the Two-Way algorithm requires only $O(1)$ constant auxiliary space. Because of this optimal space complexity and its high performance on average text, the Two-Way algorithm was adopted as the standard implementation for the strstr and memmem substring search functions in the GNU C Library (glibc).

Real-World Applications

Stream Processing and Network Intrusion Detection

Because the KMP algorithm never moves the text pointer backward, it is exceptionally well-suited for stream processing. In network security, Network Intrusion Detection Systems (NIDS) like Snort^[15] and Suricata^[16] inspect incoming packets for malicious payloads using Deep Packet Inspection. These systems read data from a network interface as a continuous, ephemeral stream. Buffering large amounts of network traffic to allow backward seeking is computationally expensive and introduces latency, potentially creating a vector for denial-of-service attacks. KMP and its variants allow these systems to scan for threat signatures in a single forward pass, maintaining high throughput.

Bioinformatics and DNA Sequencing

In computational biology^[17], researchers frequently search for specific nucleotide sequences within massive DNA databases. The DNA alphabet is very small, consisting of only four characters (A, C, G, T). Algorithms that rely on skipping characters based on the alphabet size perform poorly on small alphabets because the probability of a character mismatch allowing a large shift is low. KMP's shift logic depends entirely on the pattern's internal structure, not the size of the alphabet, making it highly effective for searching for specific nucleotide sequences^[18]. In addition, DNA sequences often contain repetitive structures, such as tandem repeats, which KMP processes optimally due to its prefix-suffix matching logic.

Hardware Acceleration

The deterministic nature of the KMP algorithm makes it highly amenable to hardware acceleration. In high-throughput environments, such as backbone network routing or massive-scale genomic sequencing, software implementations running on general-purpose CPUs may not meet performance requirements. Engineers frequently implement the KMP algorithm directly on Field-Programmable Gate Arrays (FPGAs)^[19]. Because the KMP search phase does not require backtracking, it can be mapped directly into a hardware state machine. The precomputed lps array is synthesized into hardware Look-Up Tables (LUTs) or stored in fast on-chip Block RAM. As the text stream flows through the FPGA, the hardware evaluates state transitions in parallel, often processing multiple characters per clock cycle. This hardware-level string matching achieves significantly higher throughput and lower power consumption compared to software-based approaches.

Text Editors and Standard Libraries

Historically, KMP was implemented in early text editors to provide efficient search capabilities without requiring complex memory management for backtracking. While modern general-purpose search tools (like GNU grep)^[20] often use different algorithms for faster average-case performance on standard text, KMP remains a standard algorithm implemented in various software libraries where worst-case execution time guarantees are required. It is also frequently used as a fallback mechanism when other algorithms degrade due to pathological input. Its predictable behavior makes it a popular subject for functional programming implementations.

Significance and Tradeoffs

The primary significance of the Knuth-Morris-Pratt algorithm lies in its theoretical breakthrough. It proved that exact string matching could be solved in linear time. It established the foundation for all subsequent linear-time string algorithms and demonstrated the practical utility of finite automata theory.

In modern computer architecture, the performance of an algorithm is heavily influenced by memory access patterns. KMP exhibits excellent spatial locality of reference. Because the text pointer $i$ moves strictly sequentially from left to right, the text is accessed in contiguous memory blocks. This sequential access pattern is perfectly optimized for CPU hardware prefetchers, which load upcoming text characters into the cache before they are explicitly requested.

However, in applied software engineering, KMP is not always the default choice for every search problem. The algorithm provides a strict $O(n + m)$ worst-case guarantee, but its average-case performance is also $O(n)$. It must evaluate almost every character of the text at least once.

In contrast, the Boyer-Moore algorithm^[21] (published shortly after KMP in 1977) compares characters from right to left. When a mismatch occurs, Boyer-Moore uses a "bad character heuristic" and a "good suffix heuristic" to skip multiple characters at once. For large alphabets (like ASCII or UTF-8) and long patterns, Boyer-Moore often achieves sublinear $O(n / m)$ time in practice, making it significantly faster than KMP for standard text searching. However, the original Boyer-Moore algorithm had a worst-case time complexity of $O(n \times m)$ for specific periodic patterns. In 1979, Zvi Galil introduced a mathematical modification known as Galil's rule^[22]. By recording the length of the matched suffix and preventing the algorithm from re-evaluating known matching characters, Galil's rule guarantees that Boyer-Moore operates in strict $O(n)$ linear time in the worst case, matching the theoretical guarantees of KMP while maintaining its sublinear average-case performance.

Another alternative is the Rabin-Karp algorithm^[23], which uses a rolling hash function. While Rabin-Karp has a worst-case time complexity of $O(n \times m)$ due to potential hash collisions, it is highly extensible to searching for multiple patterns simultaneously. In scenarios requiring simultaneous multi-pattern search, standard KMP requires running the search multiple times. To solve the multi-pattern problem in linear time, KMP's prefix-suffix logic was generalized into the Aho-Corasick algorithm^[24].^[31] Aho-Corasick constructs a prefix tree (trie) of all the target patterns and computes "failure links" for every node. These failure links function identically to the KMP lps array, directing the automaton to the longest possible matching prefix of any pattern in the set upon a mismatch.

KMP is chosen when the alphabet is small, when the text is a non-seekable stream, or when protection against worst-case inputs is strictly required. Its elegant use of the pattern's own internal symmetry to guide the search remains one of the most studied concepts in algorithmic design.