When I first ran into the problem of searching for a pattern inside a large body of text, my instinct was to just slide the pattern over the text one character at a time and compare. It works, but I quickly realized how wasteful it is when the pattern has repeating structure. The Knuth-Morris-Pratt algorithm, or KMP, is the classical answer to this inefficiency. It lets me search for a substring inside a string in linear time, without ever moving backward in the main text. I find that property — never re-reading a character of the text — to be the single most elegant thing about this algorithm, and it’s why KMP remains a staple in compilers, text editors, DNA sequence analysis, and intrusion detection systems.
History and Background
I trace this algorithm back to 1970, when Donald Knuth and Vaughan Pratt worked out the theoretical idea, and James H. Morris independently arrived at essentially the same approach while working on text editors. The three published their joint result in 1977 in the paper “Fast Pattern Matching in Strings.” What strikes me about the history is that Morris’s motivation was very practical — he wanted a fast way to search inside a text editor — while Knuth and Pratt approached it from a more theoretical angle related to a question about whether a certain class of languages could be recognized quickly. The convergence of a practical need and a theoretical proof into a single clean algorithm is part of why I find KMP such a satisfying piece of computer science history.
Problem Statement
I want to find every occurrence (or the first occurrence) of a pattern string P of length m inside a text string T of length n. The brute-force way to do this costs me up to O(n*m) comparisons in the worst case, because after a mismatch I throw away all the information I’ve already gathered and restart the pattern from its beginning at the next position in the text. KMP is designed to solve exactly this inefficiency: it asks how I can avoid re-examining text characters I’ve already matched, by using the structure of the pattern itself to know how far I can safely skip.
Core Concepts
Before I can explain how KMP works, I need to define a few terms I rely on throughout:
- Prefix: any leading contiguous segment of a string, including the empty string and the whole string itself.
- Suffix: any trailing contiguous segment of a string, again including the empty and full string.
- Proper prefix/suffix: a prefix or suffix that is not equal to the entire string.
- Failure function (or LPS array): for each position
iin the pattern, this stores the length of the longest proper prefix of the pattern that is also a proper suffix of the substringP[0..i]. This array is the heart of KMP. - Border: another name used in some texts for a string that is both a proper prefix and proper suffix of a given string; the failure function is really a “longest border” array.
How It Works
I break KMP into two clear phases:
- Preprocessing phase — I build the LPS (Longest Proper Prefix which is also Suffix) array for the pattern
P. This is a one-time cost ofO(m). - Searching phase — I scan the text
Tonce, using the LPS array to decide, on a mismatch, how far to shift the pattern without re-checking characters of the text I’ve already compared.
During searching, I keep two pointers: i for the text and j for the pattern.
- If
T[i] == P[j], I advance bothiandj. - If
jreaches the length of the pattern, I’ve found a match; I record it and setj = LPS[j-1]to continue searching for further occurrences. - If there’s a mismatch and
j > 0, I don’t moveibackward at all — I just setj = LPS[j-1], which tells me the longest prefix of the pattern that could still match ending at the current text position. - If there’s a mismatch and
j == 0, I simply advancei.
Working Principle
The internal logic rests on a simple but powerful observation: if I’ve already matched j characters of the pattern before hitting a mismatch, I know exactly what those j characters of text were — they were P[0..j-1]. So instead of asking “does the pattern match starting at the next text position,” which brute force does blindly, I ask “given that I already know these characters, what is the longest prefix of the pattern that I don’t have to re-verify.” That answer is precisely LPS[j-1]. This is why the text pointer i never needs to backtrack — all the information needed to decide the next alignment is already encoded in the pattern’s own self-similarity.
Mathematical Foundation
The LPS array is formally defined as:
$$ LPS[i] = \max{k : k < i+1,\ P[0..k-1] = P[i-k+1..i]} $$
for i = 0, 1, ..., m-1, with LPS[0] = 0 by convention.
The total work done across both phases is bounded because the pointer i in the text never decreases, and the pointer j can decrease at most as many times as it has increased. Formally, if I let the number of increments of i be at most n, and note that j increases at most once per increment of i, then the total decrements of j (each corresponding to an O(1) failure-function lookup) are also bounded by n. This gives:
$$ T(n, m) = O(n) + O(m) $$
for the combined preprocessing and searching phases.
Diagrams
flowchart TD
A["Start: i = 0, j = 0"] --> B{"T[i] equals P[j]?"}
B -- Yes --> C["Increment i and j"]
C --> D{"Have all pattern characters matched?"}
D -- Yes --> E["Record match and update j using LPS"]
E --> F{"Are characters remaining in the text?"}
D -- No --> F
F -- Yes --> B
F -- No --> J["End"]
B -- No --> G{"Is j greater than 0?"}
G -- Yes --> H["Update j using LPS"]
H --> F
G -- No --> I["Increment i"]
I --> FPseudocode
function buildLPS(P, m):
LPS[0] = 0
length = 0
i = 1
while i < m:
if P[i] == P[length]:
length = length + 1
LPS[i] = length
i = i + 1
else:
if length != 0:
length = LPS[length - 1]
else:
LPS[i] = 0
i = i + 1
return LPS
function KMPSearch(T, P):
n = length(T)
m = length(P)
LPS = buildLPS(P, m)
i = 0
j = 0
matches = []
while i < n:
if T[i] == P[j]:
i = i + 1
j = j + 1
if j == m:
matches.append(i - j)
j = LPS[j - 1]
else:
if j != 0:
j = LPS[j - 1]
else:
i = i + 1
return matches
Step-by-Step Example
Let me trace through a concrete case. Suppose:
- Text:
ABABDABACDABABCABAB - Pattern:
ABABCABAB
Step 1 — Build the LPS array for ABABCABAB:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Char | A | B | A | B | C | A | B | A | B |
| LPS | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 |
Step 2 — Search:
I start comparing T and P from the left. The first few characters ABAB match, then at position 4 the text has D while the pattern expects C, so I fail at j = 4. Instead of restarting j at 0, I look up LPS[3] = 2, meaning the prefix AB of the pattern is already known to match, so I resume comparison from j = 2 without moving the text pointer backward. I continue this process across the text and eventually find a full match of ABABCABAB starting at index 10 of the text.
Time Complexity
- Best case:
O(n + m)— this holds even in the best case because KMP always does a linear preprocessing pass and a linear search pass regardless of the data. - Average case:
O(n + m). - Worst case:
O(n + m)— this is the defining strength of KMP; unlike brute force, its worst case never degrades toO(n*m).
Space Complexity
I need O(m) extra space to store the LPS array. The search phase itself uses only a constant number of extra variables (i, j), so the total auxiliary space is O(m), independent of the size of the text.
Correctness Analysis
The correctness of KMP rests on proving that whenever I shift the pattern using j = LPS[j-1] after a mismatch, I never skip over a valid match. This is true because any alignment I skip would require the skipped portion of the pattern to match a portion of text that I’ve already proven (through the matched prefix) cannot equal that pattern prefix — by definition, LPS[j-1] is the longest border, so any shift smaller than what LPS dictates would necessarily reproduce a match I’ve already ruled out. Because the LPS array captures all self-overlaps of the pattern, no potential match position is ever missed, and the algorithm is provably correct by induction on the matched length.
Advantages
- Guarantees linear time
O(n + m), with no degradation on pathological inputs. - Never backtracks on the text pointer, which is valuable for streamed text I can only read once.
- The precomputed LPS array can be reused if I search the same pattern across multiple texts.
Disadvantages
- Requires
O(m)extra memory for the LPS table, unlike naive search which needs none. - The failure-function construction adds conceptual complexity compared to brute force, making it harder to implement correctly on the first attempt.
- For very short patterns or texts, the preprocessing overhead may not pay off compared to simpler methods.
Applications
I’ve seen KMP applied in:
- Text editors and word processors for “find” and “find and replace” functionality.
- Bioinformatics, for locating specific gene or protein sequences inside long DNA/RNA strings.
- Network intrusion detection systems, matching packet payloads against known attack signatures.
- Plagiarism detection tools, searching for copied phrases across large document corpora.
- Compilers and lexical analyzers, for token and keyword recognition.
Implementation in C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* Build the LPS (failure function) array for the pattern */
void buildLPS(char *pattern, int m, int *lps) {
int length = 0; /* length of the previous longest prefix-suffix */
lps[0] = 0; /* LPS[0] is always 0 */
int i = 1;
while (i < m) {
if (pattern[i] == pattern[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
/* fall back using the LPS array itself, no i increment */
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
/* Search for pattern in text, printing every match position */
void KMPSearch(char *text, char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
int *lps = (int *)malloc(m * sizeof(int));
buildLPS(pattern, m, lps);
int i = 0; /* index for text */
int j = 0; /* index for pattern */
while (i < n) {
if (text[i] == pattern[j]) {
i++;
j++;
if (j == m) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1]; /* look for the next match */
}
} else if (j != 0) {
j = lps[j - 1]; /* skip using precomputed failure links */
} else {
i++;
}
}
free(lps);
}
int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";
KMPSearch(text, pattern);
return 0;
}
Sample Input and Output
Input:
Text: ABABDABACDABABCABAB
Pattern: ABABCABAB
Output:
Pattern found at index 10
Optimization Techniques
- Combine with the Z-algorithm: for some problems I find it simpler to build a concatenated string
P + "$" + Tand use the Z-array, which achieves a similar effect to KMP with a different but equally linear technique. - Bitwise parallel matching: for short patterns (within word size), I can use the Shift-And/Shift-Or algorithm to get further practical speedups.
- Streaming search: because KMP never moves the text pointer backward, I can adapt it to work on a stream of characters without buffering the entire text, which is useful for network traffic scanning.
- Multiple pattern search: when I need to search for many patterns at once, I switch to the Aho-Corasick algorithm, which generalizes the KMP failure function idea to a trie of patterns.
Common Mistakes
- Forgetting that
LPS[0]must always be0, since a single character has no proper prefix or suffix. - Off-by-one errors when resetting
jafter a full match — it should becomeLPS[j-1], not0, so that overlapping matches aren’t missed. - Confusing the failure function with a simple “last matched index” rather than the longest proper prefix-suffix length.
- Applying brute-force fallback logic (moving
iback) after a mismatch, which defeats the entire purpose of the algorithm. - Not handling the edge case where the pattern is longer than the text.
Further Reading
- Knuth, D. E., Morris, J. H., Pratt, V. R. “Fast Pattern Matching in Strings,” SIAM Journal on Computing, 1977: https://epubs.siam.org/doi/10.1137/0206024
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. “Introduction to Algorithms” (CLRS), Chapter on String Matching: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “KMP Algorithm for Pattern Searching”: https://www.geeksforgeeks.org/dsa/kmp-algorithm-for-pattern-searching/
- Wikipedia, “Knuth–Morris–Pratt algorithm”: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
