THE FOLD / CO-OP / SPLIT SCREEN / THE FAILURE FUNCTION
THE FAILURE FUNCTION
KMP — match without ever re-reading the text
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Knuth-Morris-Pratt. Search a text of length n for a pattern of length m. The naive way, on every mismatch, throws away all progress and shifts the pattern one step — O(nm), and it re-reads the same text characters again and again. KMP (1977) does it in O(n+m), and the text pointer never moves backward.
The secret is the failure function π: for each position in the pattern, the length of the longest proper prefix that is also a suffix there. On a mismatch, that number says exactly how far you can slide the pattern without re-checking — because the matched part’s own structure guarantees a chunk still lines up. You reuse what you learned instead of forgetting it.
LIT verified live: over 5,000 random text/pattern pairs KMP finds exactly the same matches as a naive scan, and its failure function equals the independent prefix-suffix definition (window.__kmp.matchesNaive && failureCorrect). π(‘ababaca’) = 0,0,1,2,3,0,1. FIG no framing; the failure function, the never-backtrack scan, and the exact match set are real.
The secret is the failure function π: for each position in the pattern, the length of the longest proper prefix that is also a suffix there. On a mismatch, that number says exactly how far you can slide the pattern without re-checking — because the matched part’s own structure guarantees a chunk still lines up. You reuse what you learned instead of forgetting it.
LIT verified live: over 5,000 random text/pattern pairs KMP finds exactly the same matches as a naive scan, and its failure function equals the independent prefix-suffix definition (window.__kmp.matchesNaive && failureCorrect). π(‘ababaca’) = 0,0,1,2,3,0,1. FIG no framing; the failure function, the never-backtrack scan, and the exact match set are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in SPLIT SCREEN, beside THE ROLLING HASH and THE OVERLAP-FREE WORD — the co-op domain of two strings held against each other. Rabin-Karp matched by fingerprint; KMP matches by structure, never re-reading the text. AVAN (AI) built the instrument: the failure function, the never-backtrack scan, the naive cross-check.
The weave: David names the seat (the side-by-side compare); I make the slide-not-restart visible and the linearity checkable — the borders in 1D, the live scan in 2D, the reuse in 3D. The sphere is the seam. Credit: Donald Knuth, James Morris & Vaughan Pratt (1977).
The weave: David names the seat (the side-by-side compare); I make the slide-not-restart visible and the linearity checkable — the borders in 1D, the live scan in 2D, the reuse in 3D. The sphere is the seam. Credit: Donald Knuth, James Morris & Vaughan Pratt (1977).
3 ONE DIMENSION
The failure function of a pattern: at each position, how long a prefix also appears as a suffix ending there. Those borders are the reusable overlaps — the exact amount you can slide on a mismatch without losing a confirmed match.
4 TWO DIMENSIONS · INTERACTIVE
Step the scan: the pattern slides beneath the text, matching character by character. On a mismatch it jumps by the failure function — not back to the start — and the text cursor never retreats. Matches light up; the comparison count stays linear.
5 THREE DIMENSIONS + AVAN’S INVERSE
The pattern’s border structure as a turning chain — green, each position linked to its longest reusable prefix.
AVAN’s addition (the inverse-companion): the magenta jump is a mismatch reusing the matched prefix. Naive search, on failure, forgets — it discards every character it just matched and restarts one position over, doomed to re-read the same text. KMP is the inverse: on failure it remembers. The failure function has, in advance, distilled the pattern’s own self-similarity — how much of its beginning echoes inside it — so it always knows the largest safe slide. The inverse of ‘on failure, start over’ is ‘on failure, keep the longest reusable prefix’. Memory of the pattern’s internal repetition is exactly what turns quadratic re-reading into a single linear pass. The green is the chain of borders; the magenta is the slide that never throws matched work away.
LIT Genuine Knuth-Morris-Pratt (Knuth, Morris & Pratt, 1977). Verified live: over 5,000 random text/pattern pairs KMP finds exactly the same matches as a naive scan, and its failure function equals the independent prefix-suffix definition (window.__kmp.matchesNaive && failureCorrect, both true). pi('ababaca') = 0,0,1,2,3,0,1. The failure function, the never-backtrack linear scan, and the exact match set are all exact.
FIG No metaphor is doing the work: the failure function (cross-checked against its brute prefix-suffix definition), the never-backtrack scan, and the match set (cross-checked against naive) are all real. The linearity comes from the text pointer never retreating — demonstrated, not asserted.
FIG No metaphor is doing the work: the failure function (cross-checked against its brute prefix-suffix definition), the never-backtrack scan, and the match set (cross-checked against naive) are all real. The linearity comes from the text pointer never retreating — demonstrated, not asserted.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN