The shift the pattern already knows

Finding a pattern in a text is the simplest question this field asks and the one whose obvious answer is worst. Line the pattern up at position 0, compare characters until one disagrees, move the pattern one place right, do it again. It is four lines of code, it is correct, and its cost has a range of a factor of twenty-five on inputs of the same size.

The alignments, drawn #

A count is an aggregate, and the mechanism under it is a picture: each alignment of the pattern against the text is a row, and the characters that alignment actually examined are the filled cells in it.

That picture is the whole of the naive scan’s average-case defence, and it is a real defence. Over a 26-letter alphabet a random alignment agrees on its first character about one time in 26, on its first two about one time in 676, and the expected work per alignment converges to $1/(1 - 1/\sigma) \approx 1.04$ characters. Almost every row is one cell.

The trouble is that this is a statement about a distribution of inputs and the algorithm is run on whatever it is handed. On average is not a number makes the general form of this argument; the string case is unusually sharp, because the input that breaks it is not exotic. A text of repeated characters with a pattern that almost matches is what a log file of padding, a run of zeroes, or a DNA sequence over four symbols looks like from close up.

What the naive scan throws away #

Look again at the failing alignment in the hero figure. The pattern aaa…ab is lined up at position $i$, it agrees for 63 characters, and it fails on the 64th. The naive scan responds by moving the pattern to position $i+1$ and starting over from the pattern’s first character.

But it already knows what is at positions $i+1$ through $i+63$: they are all a, because it just read them and they matched. Moving one place right and re-reading them is re-deriving something it established a moment ago, and it does it 8,129 times.

The information being thrown away is entirely a property of the pattern, and that is the observation the whole algorithm is built on. When the pattern fails after matching $k$ characters, everything about the text at those $k$ positions is known: it equals the pattern’s first $k$ characters. So the question of how far the pattern may safely be shifted is a question about the pattern alone, and it can be answered once, before the text is looked at.

The failure function #

For each prefix of the pattern, the failure function records the length of the longest proper prefix of the pattern that is also a suffix of that prefix.

For abcabcabd it is [0, 0, 0, 1, 2, 3, 4, 5, 0]. Read the entry at index 7: the prefix abcabcab ends with ab, which is also how the pattern begins, and 5 says the longest such overlap is abcab. So a failure after matching eight characters can restart as though five had already matched, and the pattern may move three places rather than one — without re-reading anything.

The last entry is 0, and it is the one that makes the pattern useful. abcabcabd ends in d, which the pattern does not begin with, so a failure on the final character overlaps with nothing and the pattern restarts from scratch. A pattern with no self-overlap at all has an all-zero table and gets nothing from KMP; a pattern that is one character repeated has the table [0, 1, 2, 3, …] and gets everything.

So the table is a measurement of how self-similar the pattern is, and the algorithm’s advantage on a given pattern can be read off it before any text is seen. The hero figure’s pattern is 63 copies of one character followed by another, whose table is [0, 1, 2, …, 62, 0] — maximally self-overlapping, which is why the input is simultaneously the naive scan’s worst case and KMP’s best demonstration.

Computing it costs 10 character comparisons for that nine-character pattern, and it is computed by running the pattern against itself with the same machinery: the table for a prefix of length $i$ is found by matching the pattern against its own shifted copy, falling back through the entries already computed. A function that builds itself out of its own earlier values is a dynamic program, and this is one of the smallest useful ones there is.

The result is an algorithm whose text pointer never goes backwards. Each character of the text is read, compared against the pattern’s current position, and either matched or used to fall back through the failure function. Falls cost comparisons, but each fall strictly reduces the match length and each match increases it by one, so over the whole search there can be at most $n$ increases and therefore at most $n$ decreases.

At most $2n$ character comparisons, whatever the pattern is. That is not an average and not an expectation; it is a bound no input reaches past.

The bound is an amortised argument, and it is worth naming as one #

The argument in the paragraph above is the potential-function argument, wearing no hat. The match length $k$ is the potential: it starts at 0, ends at most at $m$, rises by exactly one on each successful comparison, and falls by at least one on each failed one. Total rises are bounded by total falls plus the final value, total comparisons are rises plus falls, and the whole thing collapses to $2n$.

That is precisely the shape what amortised means sets out for a dynamic array’s doubling, and it is worth noticing that it has appeared again in a completely different subject. The individual step here is genuinely bad — a single character of text can trigger a chain of falls the length of the pattern — and the aggregate is linear because those chains have to be paid for in advance by matches that already happened.

This also answers a question the bound invites: why $2n$ rather than $n$. The extra $n$ is the falls, and it is real. Each of them is a comparison the naive scan would not have made at that moment, and KMP is only ahead because it avoids many more.

The pointer that never goes backwards buys something else #

There is a second property of “the text pointer never moves left”, and it is not about the count at all.

KMP can run on a stream that cannot be rewound. It reads one character, updates its state, and never asks for a character it has already seen. That means it works on a socket, a pipe, or a file too large to hold, with $O(m)$ memory and no buffer.

Neither the naive scan nor the algorithm in the next essay has that property. Both go backwards — the naive scan on a failure, Boyer–Moore by design, since it compares right to left and must therefore have the whole window in hand. A search that must be able to seek is a different piece of software from one that must not.

That is not a complexity property and no counter here reports it, which is exactly why it deserves a paragraph. It is the kind of consideration that decides which algorithm ships, and it is invisible to every measurement on this page.

The bound, measured #

On the hero figure’s input — 8,192 characters, a 64-character pattern that almost matches everywhere — KMP examines 16,321 characters against a bound of $2n = 16{,}384$.

That is 99.6% of the bound, which is the most useful thing about the measurement. A guarantee that is never approached is a guarantee about a case nobody constructed; this one is nearly tight on the input the naive scan is worst on, and the two facts are the same fact. The input that maximises the naive scan’s re-reading is the input that maximises KMP’s falls.

The naive scan on the same input examines 520,256. The ratio is 31.9.

And on ordinary text it buys nothing at all #

This is the measurement worth sitting with. On the input a string search is overwhelmingly actually run on — text over a reasonably wide alphabet, with a pattern that mostly does not match — the naive scan and KMP are indistinguishable, and both are essentially $n$.

The reason is the same one that made the trace picture mostly one cell wide. On random 26-letter text almost every alignment fails immediately, so the naive scan re-reads almost nothing, so there is almost nothing for KMP to save. Its entire advantage is over work the naive scan was not doing.

That is not an argument against KMP. It is an argument about what its guarantee is for, and the distinction is exactly the one a limit is not a prediction draws: the bound describes the behaviour at the worst input, and the worst input is not the typical one. What a worst-case guarantee buys is that there is no input a caller — or an attacker — can supply that makes the search quadratic. The same shape as the depth limit that almost never fires, which costs introsort 0.14% on ordinary input and saves it a factor of 42 against an adversary.

Where it does buy something #

Over two symbols the naive scan pays 40,148 characters for a 20,000-character text and KMP pays 27,453 — a real 32% saving rather than 0.14%. Over four symbols it is 26,753 against 24,973, a 6.7% saving. Over 26 it is 0.14%.

The advantage is entirely a function of the alphabet, and it goes to zero fast.

The preprocessing is a real cost and is usually written at the back #

KMP is quoted as $O(n + m)$. Both terms are honest and the second is normally passed over, which is safe when the text is long and misleading when it is not.

The failure function for the hero figure’s 64-character pattern costs 125 character comparisons. Against a text of 8,192 that is 1.5% of the total and irrelevant. Against a text of 200 it would be more than half the work, and the algorithm that “runs in linear time” would be slower than the naive scan by a wide margin on every one of them.

This is the same arithmetic as the index that is the text makes about suffix arrays, and it is the arithmetic behind every preprocessing decision: a fixed cost paid once is worth paying when it is divided by enough queries. One search of a short text is the case where it is not.

The counter keeps the two apart on purpose. kmpSearch returns charCmp for the search and preprocessCharCmp for the table, because adding them and reporting one number would hide precisely the term that decides the question.

Lengthening the pattern on that alphabet sharpens it further, and in a direction that is easy to get backwards: a longer pattern makes the naive scan worse rather than better, because every alignment now agrees for longer before it fails.

Two counts, and they do not agree #

That figure is the honest limit of the whole comparison. When the pattern genuinely occurs everywhere, the work is not avoidable by any algorithm, and the counts converge because they are counting necessary work.

It also separates two things the phrase “worst case” runs together. The naive scan’s worst case is a text where alignments almost match — the work is wasted. This text is one where alignments do match — the work is the answer. Only the first is a defect, and only the first is what KMP fixes.

The same table says how periodic the pattern is #

The failure function is described above as a measurement of how self-similar a pattern is, and that measurement has a number in it rather than being a shape. It is one subtraction from the table’s last entry, and it is a quantity with uses outside searching entirely.

The smallest period of a pattern of length $m$ is $m - f[m]$, where $f[m]$ is the longest proper prefix that is also a suffix. A pattern equal to its own shift by $p$ has a border of length $m - p$, so the longest border and the shortest period are two readings of one fact.

For abcabcabd the last entry is 0, so the period is 9 — the pattern repeats nothing. For abab the last entry is 2 and the period is 2. For the hero figure’s aaa…ab the last entry is 0 and the period is 64, which is why that pattern is maximally self-overlapping internally and not periodic overall: every proper prefix borders heavily and the whole thing does not.

That number decides what happens after a successful match, which the essay above has not needed until now. Having found an occurrence, KMP may shift by exactly the period — the same argument as for a failure, applied to a complete match — so a pattern of period 1 shifts by one and finds every overlapping occurrence, and a pattern of period $m$ shifts the whole way and cannot overlap itself at all.

Read the degenerate input in that light and its behaviour is a consequence rather than a surprise. Four thousand identical characters searched for sixteen of the same: the period is 1, so the pattern shifts by one after every match, so it reports 4,081 overlapping occurrences and the work is the answer rather than waste. The measurement that made the three algorithms converge there is the period being 1, and the table was carrying that number the whole time.

Two further consequences are worth having, because they are free.

Periodicity is computable in linear time as a side effect of preparing to search. A great many string questions — is this text a repetition, what is its shortest generator, how many distinct rotations does it have — reduce to the period, and anybody who has built a failure function has already answered them.

And a pattern’s period bounds how much a skipping matcher can skip. No algorithm may shift past the next occurrence, so a pattern of period 1 can never shift by more than one however clever the rule, which is the reason the degenerate case defeats every matcher rather than just the naive one. That bound is in the same table, and it is the sharpest available statement of when skipping is worth building at all.

What the guarantee is actually worth #

Three statements, and they are all true at once.

KMP never exceeds $2n$. Measured at 99.6% of it on the constructed case, and that is a property no input can defeat.

On the inputs it is usually run on it saves 0.14% and costs a table, a preprocessing pass and a second control flow to get wrong.

The saving is a function of the alphabet and nothing else. Two symbols: 32%. Four: 6.7%. Twenty-six: nothing.

Standard libraries reflect all three. Almost none of them ships KMP as the default substring search; most ship a variant of the algorithm the next essay is about, which is worse in the worst case and reads a fraction of the text in the ordinary one. The exceptions are the places where an adversary chooses the input.

The one setting where the failure function is unambiguously the right machinery is the one this essay has not measured: searching for many patterns at once. Aho–Corasick builds the same fallback structure over a trie of all the patterns and finds every occurrence of every one of them in a single pass of $O(n)$ characters, where running any single-pattern algorithm $k$ times costs $k$ passes. That is a different problem with a different bound and it is not taken here; what is worth carrying from this essay is that its central idea is the one above — the failure links are the failure function, generalised from one pattern to a set of them.

That is not a criticism of KMP and it is not the usual textbook conclusion either. The usual conclusion is that KMP is the good algorithm and the naive scan is the bad one, which is a statement about a bound rather than about a measurement — and on this site a bound is not permitted to stand in for a measurement, however good the bound is.