Knuth, Morris, and Pratt: Linear-Time String Matching Without Backtracking
The Knuth-Morris-Pratt algorithm preprocesses a pattern so mismatches reuse information already learned, avoiding backtracking through the text and guaranteeing linear-time exact matching.
Text search wastes work when it forgets partial matches
A naive substring search aligns a pattern at one text position, compares characters, and after a mismatch may restart almost from the beginning. When text and pattern contain repeated prefixes, the same characters can be examined again and again.
The Knuth-Morris-Pratt algorithm avoids that repetition by preprocessing the pattern so a mismatch reveals where matching can safely resume.[1]
The pattern contains information about its own possible restart points
If a matched prefix ends with characters that are also the beginning of the pattern, the search can keep that overlap instead of discarding it. KMP turns those prefix-suffix relationships into a table used during scanning.
The 1977 paper guaranteed time proportional to pattern plus text length
Donald Knuth, James H. Morris Jr., and Vaughan Pratt published “Fast Pattern Matching in Strings” in SIAM Journal on Computing. Its abstract states that all occurrences can be found in running time proportional to the sum of the two string lengths.[1]
That guarantee was historically important because exact text search could be both practical and worst-case linear rather than merely fast on typical inputs.
The text pointer never needs to retreat
When a mismatch occurs, the algorithm changes the pattern position using its precomputed failure information. Characters already consumed from the text do not need to be rescanned from an earlier text location.
The failure function converts border structure into computation
For each prefix of the pattern, KMP records the length of the longest proper prefix that is also a suffix. NIST describes the method as turning the search string into a finite-state style matcher with O(m+n) execution time.[2]
The terminology varies—failure function, prefix function, partial-match table—but the role is the same: encode what the pattern already tells us about valid fallback states.
A mismatch can preserve useful progress
If the first several characters matched, those characters are evidence. KMP asks how much of that evidence can still be interpreted as the start of another possible occurrence.
The algorithm had multiple intellectual origins
Historical teaching material from Princeton describes KMP as a case where theory and practice met: Knuth, Pratt and Morris arrived at related pieces from different directions.[5]
James Morris’s Carnegie Mellon biography identifies him as a co-discoverer of the algorithm, while Stanford records Vaughan Pratt’s role in theoretical computer science.[3][4]
The final name records collaboration rather than a single eureka moment
The joint publication combined insights into a unified algorithm. That history is a useful corrective to stories that treat named algorithms as solitary inventions.
KMP made preprocessing a first-class algorithmic tradeoff
The method spends O(m) time examining the pattern before scanning the text. That small upfront cost creates a search automaton specialized to one pattern.
This is a recurring design strategy: compile information about a query into a data structure once so repeated or long-running execution becomes simpler and faster.
String matching became important far beyond text editors
Exact substring search appears in compilers, command-line tools, document processing, biological sequence analysis and protocol inspection. The KMP paper itself discusses text editing and more general pattern-matching problems.[1]
Later systems often choose other algorithms because constants, alphabets or hardware change the tradeoff, but KMP remains a standard reference point because its linear worst-case reasoning is so clear.
KMP sits beside, not above, other string-search strategies
Boyer-Moore often skips farther on typical text by comparing from the pattern’s right side, while hashing-based methods trade exact character comparisons for rolling fingerprints. KMP’s historical importance is its deterministic left-to-right guarantee rather than universal dominance.
That diversity demonstrates a broader lesson: “best” algorithm depends on workload, guarantees, preprocessing budget and machine behavior.
Why KMP belongs in coding history
KMP turned repetition inside a pattern from a source of wasted work into useful state. The algorithm remembers enough about previous comparisons to avoid doing them again.[1][2]
Its lasting lesson is one of information reuse: after a computation fails, ask what the failure itself has taught you before starting over.
Works Cited
- 01
- 02
- 03
- 04Stanford University — Vaughan Pratt profile engineering.stanford.edu
- 05Princeton University COS 226 — Substring Search / KMP history cs.princeton.edu
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead