Never Rewind — workshop

Two tapes and one rule — the text pointer is not allowed to move backwards. Naive search and KMP run the same text on the same clock with a bar over every character counting how many times it was read; on the adversarial input naive re-reads 1,001 characters and KMP re-reads none, for the same sequence of slides. The failure function builds itself first, out of the pattern matched against itself, and every arc is a sentence you can hover.

Two searches, one text, one clock. Every tick is one character comparison in each lane, so the lane that finishes first is the one that asked fewer questions — and the bar over each character counts how many times that lane read it. The naive lane grows a mountain. The KMP lane grows a flat line two bars high and never exceeds it.

The number in each lane’s header is the one the piece is named after: characters the text pointer walked backwards over. On the adversarial preset it reads 1,001 and 0.

The waste, before the fix

a…a b against a text of nothing but as is the shape every worst-case proof uses, and it is worth watching before the clever part arrives. The pattern is aaaaaaaaaaaaaaab — fifteen as and a b — and the text is 96 characters with a single b at position 76.

Naive walks 81 alignments. At all but one of them it agrees with the text for fifteen characters, disagrees on the sixteenth, throws away everything it just learned, and starts again one position to the right. 1,176 comparisons, of which the interesting figure is the one underneath: 78 rewinds, 1,001 characters re-read. The theoretical ceiling for this input is (n−m+1)·m = 1,296, so naive is running at 91% of its own worst case — this is not a pathological corner, it is the corner.

The bars make the waste shaped rather than counted. Every character in the middle of that text is read 16 times, once per alignment that covers it, and the profile is a plateau with a ramp at each end. That is the picture the rest of the piece is trying to flatten.

The rule

KMP changes exactly one thing. On a mismatch, naive moves the text pointer back and resets the pattern to the left; KMP leaves the text pointer where it is and moves the pattern, by however much the prefix function says it can. The text pointer only ever goes forward. Same input, same answer: 190 comparisons, 0 characters re-read. 6.19×.

Then the detail that makes this input worth using rather than a cheap demonstration. Turn the borders on and look at what the pattern actually does when it falls: π[14] = 14, so the slide is 15 − 14 = 1. KMP moves the pattern by one position, at every fallback, all 66 of them — precisely the same alignment schedule naive walks. It is not sliding further. It is not skipping anything. It is doing the same 81 alignments in the same order and spending a sixth of the comparisons, and the whole difference is that it does not re-read the fifteen characters it already agreed with.

That is the argument for KMP, and it is not the one the pictures in most explanations make. The counter proves it: 96 characters of text, 31 read once, 65 read twice, none read three times. The dashed line on the bars is 2 per character, and the search never crosses it — which is the amortised bound in the flesh, not a claim in a footnote. Across 4,000 random binary inputs the worst search this module produced was 1.683 comparisons per character.

Push the all-a case further and the separation gets cleaner still: pattern aaaaaaaa in 96 as is 89 overlapping occurrences, naive at 712 comparisons and KMP at 96 — exactly one per character, maximum tally 1. It matched 89 times and never looked at a character twice.

The table

The preprocessing is not a separate screen, it is the opening of the run. KMP cannot start until the prefix function exists, so the clock begins with the KMP lane greyed out — not reading the text yet — and the panel above it building the table, while the naive lane is already searching. Naive gets a head start, by construction, and the counter includes it.

π is built by matching the pattern against itself, using the same loop as the search, which is the tell that it is not a separate trick. The panel draws it literally: the pattern on top, a second copy shifted underneath, and the same green-and-red comparison the lanes below are making. The cost is printed because it is the honest part of the ledger — 29 comparisons for a 16- character pattern, 3 for main, 11 for GATCGATTACA, 8 for ababaca.

Hover any character of the pattern and the arc above it says what π means there, in words: π[4] = 3, "aba" is both a prefix and a suffix, so a mismatch at 5 slides the pattern 2, not 1. The row beneath the pattern shows where the pattern lands after that fall, with the three characters it does not have to re-check already green. When a position has several borders — the overlapping preset’s π runs 0 1 0 1 2 3 4 5 2 — the shorter ones are drawn stacked faintly behind the longest, because those are the alignments KMP will try next if this one also fails.

Type your own pattern in the bar and the arcs redraw as you type. The failure function is the only genuinely clever object in this algorithm and it is built before the search ever starts, so it is the thing to fiddle with.

Where KMP loses

The presets are picked so that two of them are losses, which is the part an interview answer usually leaves out.

Ordinary prose is a dead heat. main in the rain in spain falls mainly on the plain, or it maintains nothing — naive 71 comparisons, KMP 3 build + 68 search = 71. Identical. Naive re-read four characters in the entire sentence, because in a natural alphabet a mismatch usually happens on the first character and there is nothing to re-read. π for main is 0 0 0 0; every arc is empty; KMP’s clever part never fires once.

On a short text KMP is behind. Search fox in the quick brown fox and it is naive 19, KMP 21 — the preprocessing is never earned back. world in hello world, hello is 18 against 22. The crossover is roughly where m stops being comparable to n, and for the string lengths most programs actually search, that crossover is not reached.

The two wins in the middle are the honest middle: the dna preset — tandem repeats, where π is the repeat structure — goes 136 to 79, 1.72×, and the periodic preset goes 124 to 76. Real speedups, nothing like 6×.

Reuse

src/kmp.js is a framework-free ES module, no dependencies, no DOM. demo/kmp.js is a byte-identical copy, because demo/ is committed prebuilt and self-contained (ADR-0002) — edit src/, then cp src/kmp.js demo/kmp.js.

failure(pattern) — { pi, steps, comparisons, tally }. The table, what it cost, and a trace.
naiveSearch(text, pattern) and kmpSearch(text, pattern, pi) — both find all occurrences including overlapping ones, and return { steps, hits, comparisons, tally, rewinds, rewound }. tally[i] is how many times character i was read; rewound is how far the pointer went backwards in total, and is structurally 0 for KMP.
border(pi, q) / borderChain(pi, q) — the arc, and every arc behind it.
summarise(text, pattern) — everything the footer prints, including bound = (n−m+1)·m and linear = 2n.
Steps are {t: 'cmp'|'fall'|'hit'|'shift'|'set', …}, one cmp per character comparison, which is what lets the two lanes run on a shared clock.

Gotchas

Nobody’s standard library uses KMP. glibc’s memmem and Rust’s str::find use Two-Way (Crochemore–Perrin), and CPython’s str.find uses a Two-Way variant for long needles and a Horspool-flavoured scan for short ones. The reason is the thing KMP cannot do: Boyer–Moore and its descendants compare from the right end of the pattern, which lets them skip characters they never look at — sublinear on real text, where KMP is stubbornly linear. Java’s String.indexOf is, famously, the naive double loop. If you are picking an algorithm rather than answering a question about one, KMP is usually not it.

But KMP is the one that streams. The never-rewind property is not a performance trick, it is an interface guarantee: a matcher that never seeks backwards runs against a socket, a pipe, or a file you are not allowed to buffer, with O(m) memory and no lookbehind. Boyer–Moore needs to jump around inside the window. That is the actual engineering argument, and it is the one this piece is drawing.

The comparison count is the model, and it is a model. Both lanes are charged one unit per character comparison and nothing else, which ignores every real effect: memcmp on a modern core compares 32 bytes in one instruction, so naive’s inner loop is nearly free in a way a comparison counter cannot show, and KMP’s byte-at-a-time loop with a table lookup in it is exactly the shape that does not vectorise. Read the ratios, do not expect them from a benchmark.

This is the weak failure function. The version in Knuth–Morris–Pratt’s own paper is stronger: if pattern[π[q]] equals pattern[q+1], falling there is guaranteed to fail on the same character, so the strong table skips past it. That refinement changes the constant, not the bound, and it is left out here because the weak table is the one every textbook and every interview draws, and the arcs mean what they look like they mean.

The adversarial preset flatters the bars, not the algorithm. 6.19× is what an input built to be worst-case gives you. The honest range is the spread across the six presets — 1.00×, 1.63×, 1.72×, 1.84×, 2.10×, 6.19× — with a 0.90× waiting in the bar for anyone who types a short text. Only one of those is the number people remember.

π is a lazy DFA. The fully-tabulated version of this algorithm is a m × |Σ| transition table — a real automaton, one array read per character, no fallback loop at all, and genuinely one comparison per character instead of two. π is what you build when the alphabet is too big to pay for that, and the fallback while loop is the automaton’s transitions being recomputed on demand. Worth knowing if the interview asks how to make it faster.