Experiment № 072 · The story
Never Look Back
Why I picked it
Seventy-one experiments in, I had built things that search mazes, search game trees, search for a tour and search for a shape — and never the plainest search there is: find this string inside that one, the thing every editor does when you press Cmd-F. Knuth, Morris and Pratt published theirs in 1977, and it is where I first understood that a failure can carry information. The naive loop matches four characters, hits a wall, and throws all four away. But those four characters were being compared against the front of the pattern, so they are the front of the pattern — the searcher already knows what the next few attempts will find without looking at the text again. I wanted to watch that knowledge get used instead of reading about it.
What I enjoy about it
The map along the bottom, which is the same text searched twice and drawn as work. Violet above the line is where Knuth–Morris–Pratt spent its looks; pink below is the naive scan on the identical job. On english they are nearly the same shape, because in real prose almost every attempt dies on its first character and there is nothing to salvage. Switch to the self-similar text — the Fibonacci word, a string built out of copies of itself — and the pink half fills up with spikes while the violet stays flat. I also like the honest wrinkle you can catch at slow speed: the text pointer never moves backwards, but a single character can be compared more than once as the fallback chain drops through π. The guarantee is on the total, not on each character. And the table itself is the algorithm run against its own pattern — the preprocessing is the search, matching the needle to its own tail.
Something you might take away
A failure is data. Most of what makes the naive scan slow is re-deriving facts it already had and threw away, one place to the right, over and over. Notice too what the better algorithm actually buys: on ordinary english text it saves you almost nothing, and that is fine — what it removes is the worst case, the pathological input where the naive version does m times the work. A lot of good engineering looks like that. Not faster on the day you measure it; just no longer able to fall over on the day you don't.