THE FOLD / GRIND / THE HOT LOOP / THE KMP
THE KMP
a search that never looks back
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Knuth–Morris–Pratt algorithm finds a pattern inside a text in linear time, never looking back in the text. Its secret is the failure function: for each pattern position, the length of the longest proper prefix that is also a suffix there. On a mismatch, instead of shifting by one and re-reading, KMP jumps the pattern forward by what the failure function already knows — the text pointer only ever moves forward. The whole search costs at most about 2n character comparisons for a text of length n.
LIT verified live: over 3,000 random text/pattern pairs, the failure function matches its definition, KMP finds exactly the same match positions as naive search, and the comparison count stays under 2n (window.__kmp). FIG no framing; KMP, the naive matcher, and the comparison counter all run in-browser.
LIT verified live: over 3,000 random text/pattern pairs, the failure function matches its definition, KMP finds exactly the same match positions as naive search, and the comparison count stays under 2n (window.__kmp). FIG no framing; KMP, the naive matcher, and the comparison counter all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hot-loop — the search is the hot loop, and KMP keeps it tight: one forward pass, no rescanning. AVAN (AI) built the instrument: the failure-function builder, the KMP scan with its comparison counter, and a naive matcher to check every result.
Credit as content: Donald Knuth, James H. Morris & Vaughan Pratt (1977). The weave: David names the hot loop; I confirm the failure function is correct, that KMP finds the same matches as brute force, and that it stays linear.
Credit as content: Donald Knuth, James H. Morris & Vaughan Pratt (1977). The weave: David names the hot loop; I confirm the failure function is correct, that KMP finds the same matches as brute force, and that it stays linear.
3 ONE DIMENSION
The pattern with its failure-function value under each character — how far to jump the pattern on a mismatch without re-reading the text.
4 TWO DIMENSIONS · INTERACTIVE
A text and a pattern; KMP marks every occurrence and counts its comparisons — matched against naive search.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the text scanned once, the pointer only moving forward.
AVAN’s addition (the inverse-companion): don’t rescan the text — read the pattern’s self-overlap. The inverse of ‘shift by one and compare again’ is ‘the failure function already encodes how much of the match survives, so the text never rewinds.’ Magenta is a mismatch jump; green is a found match. The pattern knows itself.
LIT Genuine Knuth–Morris–Pratt (Donald Knuth, James Morris, Vaughan Pratt, 1977): linear-time string matching via the prefix-function. Verified live: failure function matches its brute definition (window.__kmp.failureCorrect), KMP's matches equal naive search (.matchesNaive), and comparison count ≤ 2n (.linear).
FIG No framing: KMP, a naive matcher, and a comparison counter all run in-browser and agree over 3000 pairs. The AVAN inverse is honest — reading the pattern's self-overlap (the failure function) so the text never rewinds, rather than shifting by one and re-reading, is the algorithm's whole idea; magenta is the forward-only text pointer, green a found match. The pattern knows itself.
FIG No framing: KMP, a naive matcher, and a comparison counter all run in-browser and agree over 3000 pairs. The AVAN inverse is honest — reading the pattern's self-overlap (the failure function) so the text never rewinds, rather than shifting by one and re-reading, is the algorithm's whole idea; magenta is the forward-only text pointer, green a found match. The pattern knows itself.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOT LOOP · David Lee Wise (ROOT0), with AVAN