I use the Knuth-Morris-Pratt (KMP) algorithm whenever I need to search for occurrences of a pattern string within a text string efficiently, without the wasted work that a naive approach incurs from repeatedly re-checking characters I’ve already compared. I consider KMP an essential building block in string processing because it guarantees linear-time matching, which I rely on constantly in text editors, search utilities, bioinformatics tools, and network intrusion detection systems.
History and Background
I trace the KMP algorithm to a 1970 discovery by Donald Knuth and Vaughan Pratt, developed independently around the same time by James H. Morris, with all three ultimately publishing the combined result in 1977 as “Fast Pattern Matching in Strings” in the SIAM Journal on Computing. I note that the motivation partly came from a theoretical result by Cook that showed pattern matching could be done on a certain class of automata within linear time, which Knuth, Morris, and Pratt then turned into a practical, implementable algorithm. I regard this discovery as a foundational moment in string algorithms, since it was among the first to demonstrate that avoiding redundant comparisons through clever preprocessing could take a quadratic-looking problem down to linear time.
Problem Statement
I use KMP to solve the classic pattern-matching problem: given a text $T$ of length $n$ and a pattern $P$ of length $m$, I want to find all occurrences (or the first occurrence) of $P$ within $T$. I want to avoid the inefficiency of the naive algorithm, which in the worst case re-examines characters of $T$ multiple times, leading to $O(nm)$ time. I want an algorithm that never needs to move backward in the text, examining each text character a bounded number of times.
Core Concepts
I rely on the concept of the failure function (also called the prefix function or partial match table), denoted $\pi$, where $\pi[i]$ represents the length of the longest proper prefix of $P[0..i]$ that is also a suffix of $P[0..i]$. I use this table to determine, upon a mismatch during matching, exactly how far I can safely shift the pattern without missing any potential match — because I already know, from the failure function, which portion of the pattern I’ve already confirmed matches.
How It Works
I follow this two-phase process when performing KMP matching:
- Preprocessing phase: I compute the failure function $\pi$ for the pattern $P$, which encodes self-overlap information within the pattern itself.
- Matching phase: I scan the text $T$ left to right, comparing characters against the pattern. When I find a mismatch at pattern position $j$, instead of restarting the pattern comparison from the beginning, I use $\pi[j-1]$ to determine the next pattern position to compare from, without moving the text pointer backward.
- Whenever I match the entire pattern (reach $j = m$), I record a match and continue searching by resetting $j$ to $\pi[j-1]$, in case there are overlapping occurrences.
Working Principle
I understand the internal logic of KMP as exploiting the self-similarity of the pattern to avoid redundant work. When a mismatch occurs after matching some prefix of the pattern, I know exactly which characters of the text I’ve already seen (they match a prefix of the pattern). Since the failure function already tells me the longest prefix of the pattern that is also a suffix of what I’ve matched so far, I can “slide” the pattern forward to align this known-good suffix with the corresponding prefix, without ever needing to re-examine text characters I’ve already compared. This is the key mechanism that keeps the text pointer moving strictly forward throughout the entire algorithm.
Mathematical Foundation
I define the failure function formally:
$$ \pi[i] = \max{ k : k < i+1, \ P[0..k-1] = P[i-k+1..i] } $$
with $\pi[0] = 0$ by convention (a single character has no proper prefix).
I prove the linear-time bound of the matching phase using an amortized analysis based on a potential function. I define the potential as the current value of $j$ (the number of pattern characters matched so far). I note that:
- Each successful character comparison increases $j$ by 1, and the text pointer $i$ also always increases by 1 per outer loop iteration.
- Each failed comparison decreases $j$ (via $j = \pi[j-1]$) but does not increase $i$.
Since $j$ can increase at most $n$ times total (bounded by the number of times $i$ advances) across the entire matching phase, and each decrease of $j$ must be “paid for” by a prior increase, I conclude the total number of comparisons is bounded by $2n = O(n)$.
I similarly bound the failure function computation itself at $O(m)$ using the identical amortized argument applied to the pattern against itself.
Diagrams
flowchart TD
A[Input: text T, pattern P] --> B[Compute failure function pi for P]
B --> C[Initialize text pointer i = 0, pattern pointer j = 0]
C --> D{T i equals P j?}
D -->|Yes| E[Increment i and j]
E --> F{j equals length of P?}
F -->|Yes| G[Record match at i - j]
G --> H[Set j = pi j-1, continue]
F -->|No| I{i reached end of T?}
D -->|No, and j > 0| J[Set j = pi j-1]
J --> D
D -->|No, and j == 0| K[Increment i only]
K --> I
H --> I
I -->|No| D
I -->|Yes| L[Return all matches]
Pseudocode
I write the pseudocode for computing the failure function and performing the search:
function COMPUTE_FAILURE(P):
m = length(P)
pi = array of size m, initialized to 0
k = 0
for i from 1 to m - 1:
while k > 0 and P[i] != P[k]:
k = pi[k - 1]
if P[i] == P[k]:
k = k + 1
pi[i] = k
return pi
function KMP_SEARCH(T, P):
n = length(T)
m = length(P)
pi = COMPUTE_FAILURE(P)
j = 0
matches = empty list
for i from 0 to n - 1:
while j > 0 and T[i] != P[j]:
j = pi[j - 1]
if T[i] == P[j]:
j = j + 1
if j == m:
matches.append(i - m + 1)
j = pi[j - 1]
return matches
Step-by-Step Example
I search for pattern $P = \text{“ababaca”}$’s failure function first, then match text $T = \text{“bacbababaca”}$ against $P = \text{“ababaca”}$.
Computing $\pi$ for “ababaca”:
| i | P[i] | k before | k after | pi[i] |
|---|---|---|---|---|
| 0 | a | – | – | 0 |
| 1 | b | 0 | 0 | 0 |
| 2 | a | 0 | 1 | 1 |
| 3 | b | 1 | 2 | 2 |
| 4 | a | 2 | 3 | 3 |
| 5 | c | 3 | 0 | 0 |
| 6 | a | 0 | 1 | 1 |
I obtain $\pi = [0, 0, 1, 2, 3, 0, 1]$.
Matching against $T = \text{“bacbababaca”}$:
I scan through the text, and I find that starting at text index 4, the substring “bababaca”… wait, I check carefully: at $i=10$ (0-indexed, end of text), I complete matching the full pattern “ababaca” starting at text index 4. I record a match at position 4, and thanks to the failure function, I never had to move the text pointer backward even when earlier partial matches failed.
Time Complexity
I establish that KMP runs in $O(n + m)$ time overall: $O(m)$ for computing the failure function and $O(n)$ for the matching phase, both justified by the amortized analysis in the Mathematical Foundation section. This bound holds in the best, average, and worst case alike — unlike the naive algorithm, whose worst case is $O(nm)$ (for example, matching “aaaa…a” against a long run of a’s), KMP guarantees linear time regardless of the input’s specific structure, because the text pointer never moves backward.
Space Complexity
I require $O(m)$ additional space to store the failure function table, where $m$ is the pattern length. I need no extra space proportional to the text length $n$, since I process the text in a single forward pass using only a constant number of index variables ($i$, $j$) beyond the failure table itself.
Correctness Analysis
I justify the correctness of the failure function computation by induction on $i$: I assume $\pi[0..i-1]$ are all correct, and I show that the while loop, which repeatedly falls back to $\pi[k-1]$ upon mismatch, correctly finds the longest proper prefix-suffix match for position $i$ by trying progressively shorter candidate overlaps until one succeeds or none remain. I justify the matching phase’s correctness similarly: whenever a mismatch occurs, falling back to $j = \pi[j-1]$ preserves the invariant that the characters of $T$ already compared still match the corresponding prefix of $P$ up to the new, shorter value of $j$ — no valid match is ever skipped, because any match starting within the discarded region would have required a longer prefix-suffix overlap than $\pi[j-1]$ allows, which the failure function already ruled out as impossible.
Advantages
- I guarantee linear-time, $O(n+m)$, matching regardless of the input, unlike the naive algorithm’s worst-case quadratic behavior.
- I never need to backtrack in the text, which makes KMP suitable for streaming input where I cannot re-read previous characters.
- The failure function preprocessing is reusable across multiple searches of the same pattern against different texts.
- KMP is deterministic and doesn’t rely on hashing, so I avoid the (rare) risk of hash collisions that algorithms like Rabin-Karp face.
Disadvantages
- I find the failure function construction and the fallback logic conceptually more intricate than simpler (though slower) algorithms like the naive approach or even Boyer-Moore’s simpler heuristics.
- KMP does not take advantage of information about the alphabet size the way Boyer-Moore’s bad character heuristic does, so in practice it can be slower than Boyer-Moore on typical English text searches.
- Implementing KMP correctly requires careful off-by-one handling in the failure function and matching loop, which I find is a common source of bugs.
- KMP handles only exact string matching; it does not natively support approximate matching or wildcards without significant modification.
Applications
I apply KMP in:
- Text editors and search utilities: implementing fast “find” functionality.
- Bioinformatics: searching for DNA or protein subsequences within large genomic datasets.
- Network security: intrusion detection systems scanning packet payloads for known attack signatures.
- Data compression: some LZ-family compression algorithms use KMP-like matching to find repeated substrings.
- Plagiarism detection: searching for exact matching passages across large document corpora.
Implementation in C
I implement the KMP algorithm in C, with comments:
#include <stdio.h>
#include <string.h>
// I compute the failure function (partial match table) for pattern P
void computeFailure(char* P, int m, int* pi) {
pi[0] = 0;
int k = 0;
for (int i = 1; i < m; i++) {
while (k > 0 && P[i] != P[k]) {
k = pi[k - 1]; // I fall back using the failure function
}
if (P[i] == P[k]) {
k++;
}
pi[i] = k;
}
}
// I search for pattern P within text T using the KMP algorithm
void kmpSearch(char* T, char* P) {
int n = strlen(T);
int m = strlen(P);
int pi[m];
computeFailure(P, m, pi);
int j = 0; // number of characters of P currently matched
for (int i = 0; i < n; i++) {
while (j > 0 && T[i] != P[j]) {
j = pi[j - 1];
}
if (T[i] == P[j]) {
j++;
}
if (j == m) {
printf("Match found at index %d\n", i - m + 1);
j = pi[j - 1]; // I continue searching for further matches
}
}
}
int main() {
char T[] = "bacbababaca";
char P[] = "ababaca";
kmpSearch(T, P);
return 0;
}
Sample Input and Output
I use T = "bacbababaca" and P = "ababaca" as input, and I expect:
Match found at index 4
Optimization Techniques
- I precompute and cache the failure function whenever I need to search for the same pattern across multiple texts, avoiding redundant preprocessing.
- I combine KMP with the Aho-Corasick algorithm when I need to search for multiple patterns simultaneously, extending the failure-function idea to a trie structure.
- I use bitwise parallel matching techniques (like the Shift-And/Shift-Or algorithm) as an alternative when the pattern is short enough to fit within machine word size, sometimes outperforming KMP in practice.
- I apply KMP’s failure function concept in related string algorithms, like computing the shortest period of a string, since $m – \pi[m-1]$ gives the length of the smallest repeating unit.
Common Mistakes
- I sometimes confuse the failure function index conventions (0-indexed vs 1-indexed), leading to off-by-one errors in the fallback logic.
- I forget to reset $j$ using the failure function after finding a match, missing overlapping occurrences of the pattern.
- I incorrectly initialize $\pi[0]$ to a nonzero value, violating the definition that a single character has no proper prefix.
- I mistakenly apply the naive matching logic (resetting $j$ to 0 on every mismatch) instead of using the failure function, which silently degrades performance back to quadratic time while still “working” on small test cases.
- I overlook edge cases like an empty pattern or a pattern longer than the text, causing out-of-bounds access.
Further Reading
- Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). “Fast Pattern Matching in Strings.” SIAM Journal on Computing: https://epubs.siam.org/doi/10.1137/0206024
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms (string matching chapter): https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Gusfield, D. Algorithms on Strings, Trees, and Sequences: https://www.cambridge.org/core/books/algorithms-on-strings-trees-and-sequences/F0B095049C7E62D2FF6746DE39D65D22
- MIT OpenCourseWare, 6.006 Introduction to Algorithms (string matching lecture): https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- GeeksforGeeks, “KMP Algorithm for Pattern Searching”: https://www.geeksforgeeks.org/dsa/kmp-algorithm-for-pattern-searching/
