KNUTH-MORRIS-PRATT the search that never looks back
Boyer-Moore (dart 061) reads the pattern backwards; KMP reads forwards but never re-reads a character of the text. On a mismatch it slides the pattern by exactly how much its own prefix repeats — a number precomputed into a failure table. Linear time, guaranteed. The table is an array, so it runs in real I-13.
THE TECHNIQUE the failure table = borders of prefixes
For each position in the pattern, precompute the length of the longest proper prefix that is also a suffix (a border). On a mismatch, jump the pattern forward by that much and keep the text pointer where it is — no character is read twice. Search below; the table is shown, and the text pointer only ever moves right. live demo
HISTORY & CREDIT two discoveries, one paper
One name, “KMP” — but it was found once twice, from opposite directions, and merged. cited
1969–70 · James H. Morris devises it (1969, to avoid backing up a text-editor buffer); with Vaughan Pratt it becomes a 1970 Berkeley report (the Morris-Pratt method). By discovery Morris was first — “KMP” is alphabetical order, not priority. ~1970 · Donald Knuth, hand-running Cook’s theorem on two-way deterministic pushdown automata (2DPDA), derives essentially the same search from pure theory — then was, in his words, “chagrined to learn Morris had already discovered the algorithm.” The first time automata theory taught him a better real algorithm. 1977 · the three publish jointly, “Fast Pattern Matching in Strings” (SIAM J. Computing, June) — the same year as Boyer-Moore (CACM, October), not the same issue. Pratt’s piece is the strong next table; the plainer Morris-Pratt border is what textbooks show. the guarantee · O(n+m), worst-case linear — unlike Boyer-Moore’s original, whose sublinear speed is only average-case.
The failure function is the same idea as the border array and underlies Aho-Corasick and the Z-algorithm. theory made practical
RECOMMEND FOR I-13 the failure table is an array
KMP is two array passes: build the failure table over the pattern, then scan the text with two indices that only advance. Both are indexed reads and comparisons on the bounded array:
# failure table of "ABABAC"
fail = [0, 0, 1, 2, 3, 0] # longest border at each position
# scan: the text pointer never retreats -> O(n+m)
Recommend:nothing new — the failure table is a bounded array of small integers, the scan is two advancing indices with character equality, all f64-representable. Like Boyer-Moore (061) the only slightly awkward part is a list of match positions as output (the array-return / multiple-return frontier); the search core is a clean no-wall. Note: where Boyer-Moore jumps far on a mismatch (great on natural text), KMP guarantees linear worst-case — two answers to the same question, both bounded-array work.