Change the pattern to one the text does not contain and the asymptotically better algorithm loses. Naive matching makes exactly one comparison per alignment, n − m + 1 in total; KMP reads every character of the text once, n in total. The difference is m − 1 in naive's favour on every such text, which makes this the clearest instance on the path of a count that says nothing about a bound.
Core ideas
The hard idea is that the loss is structural, not noise. The other two are the exact counts each algorithm makes and what a guarantee is actually for.
When no character of the text equals p[0], every naive alignment ends after one comparison, so the total is the number of alignments, n − m + 1. KMP holds a matched-length k that stays at 0 throughout and makes exactly one comparison for each character of the text, so its total is n. Since n exceeds n − m + 1 by m − 1, naive wins by m − 1 on every such text — 4 here, and more for a longer pattern.
KMP's promise is that the text pointer never moves backwards and the total stays under 2n. On this input it makes 43 comparisons against a bound of 86, so the promise is kept with room to spare. What it is not is a promise to beat the naive matcher on any particular text, and nothing in the proof of 2n ever claimed that. A guarantee bounds the bad case; it does not improve the good one.
This text settles “KMP always makes fewer comparisons than naive matching”, and settles it negatively, because one counterexample is enough to kill a universal statement. The same text establishes nothing at all about “naive matching is faster than KMP”, because no number of examples adds up to a quantifier. The asymmetry is the whole method of this Subject: measurements refute, and only proofs confirm.
The material
Why each count is what it is, why the reversal is guaranteed rather than lucky, and what KMP is being paid for if not this.
Keep the text from the previous page and change the pattern from ain to zebra. There is no z anywhere in the rain in spain stays mainly in the plain, so no alignment gets past its first comparison. The lab reports 39 comparisons over 39 alignments, at exactly 1 per alignment, against a bound of 5 × 39 = 195.
If no character of t equals p[0], the naive matcher makes exactly n − m + 1 comparisons and reports no match.
Each alignment begins by comparing t[i] with p[0]. By hypothesis these differ, so the inner loop stops with k = 0 after one comparison, and the alignment reports nothing.
There are n − m + 1 alignments and each contributes exactly 1, so the total is n − m + 1. No alignment reaches k = m, so no match is reported, which is correct because a match would require t[i] to equal p[0].
□
If no character of t equals p[0], KMP makes exactly n comparisons.
KMP maintains k, the number of pattern characters currently matched, starting at 0. Its fallback loop runs only while k > 0.
Suppose k = 0 on entering the step for text position i. The fallback loop is skipped, one comparison of t[i] against p[0] is made, and by hypothesis it fails, so k stays 0. By induction k is 0 at every position, so exactly one comparison happens at each of the n positions and the total is n.
□
Subtract: n − (n − m + 1) = m − 1. On this input that is 4, and the panel reports 39 against 43. The margin does not depend on the text at all, only on the length of the pattern, so lengthening zebra to zebraic widens it to 6 without touching either algorithm.
The growth table repeats the text and the two columns stay apart in the same direction. Naive reads 39, 82, 125, 168, 211, 254 as n runs 43, 86, 129, 172, 215, 258, and KMP reads 43, 86, 129, 172, 215, 258 — which is n itself, in every row. The difference is 4 in every row, because it is m − 1 and m never moved.
Switch the preset to the one built to reach the bound and read the same two columns: naive 100, KMP 44, on a text of 24 characters. KMP is not better on average here or worse on average there; it is the algorithm whose count cannot exceed 2n whatever is typed, and naive matching is the algorithm whose count cannot exceed m(n − m + 1). At n = 24 and m = 5 those two ceilings are 48 and 100, and the measured numbers sit under each.
So the honest summary of the pair of experiments is: the measured counts reverse between two texts, and the bounds do not. Whichever direction you want to argue, the evidence for it is a proof and the numbers are illustrations.
The third column reports 14. Horspool compares the window from the right and then shifts by the last occurrence of the text character sitting under the window's final position, which for a letter absent from the pattern is the full m. So it reads roughly one character in five and finishes in 14 comparisons where naive needs 39.
That is the largest saving on the page and the one with the least behind it. Horspool's worst case is m(n − m + 1) comparisons, the same as naive's, and the sibling lesson “The Text Where Nothing Is Skipped” is a 30-character text on which it makes 130 comparisons and naive makes 26.
Put the three side by side and the ordering changes twice in this course with no algorithm changing at all. That is the point: the ranking is a property of the input, and the only statements that survive every input are the bounds, which do not rank them at all.
Interactive
Comparisons measured per alignment, against m and against m(n − m + 1)
Method
One input can kill a universal claim outright and can never establish one. Keep those two uses apart.
“KMP makes fewer comparisons” has to be finished: fewer on every text, or fewer on this one. The first is refuted by the input on screen. The second is a measurement and generalises to nothing.
Here it is structural: the two counts are n − m + 1 and n exactly, both proved, so the margin m − 1 holds on every text with no z in it. An incidental reversal would move when the text moved, and this one does not.
39 against a bound of 195, and 43 against a bound of 86. The algorithm that lost the measurement has by far the tighter guarantee, and a page showing only the measurements would have hidden that.
The same lab, one click away, has naive at 100 and KMP at 44. If a sentence you were about to write survives only one of the two presets, it is a sentence about a text.
The text is the rain in spain stays mainly in the plain, 43 characters, and the pattern is zebra, 5 characters. No z occurs in the text.
Nothing in that table was read off the screen except the last line. The two totals and the margin follow from the two theorems above and the two lengths, which is what makes this a reversal you can predict rather than one you notice.
For a faded rehearsal, keep the text and change the pattern to quartz. The supplied first move: there is no q in the text either, so the same two theorems apply with m = 6. Say what the three counts become — naive, KMP, and the margin — before running it, and then say which of the three you could have got wrong by assuming the margin was a property of the text.
Then try plain, which does occur. Now p appears twice in the text, so the first theorem no longer applies and the naive count is no longer the alignment count. Predict whether naive still beats KMP, and say what you would have to know about the text to answer that without running it.
You should be able to prove that naive makes n − m + 1 comparisons and KMP makes n when the text avoids p[0], derive the margin m − 1 without running anything, state why this refutes a universal claim but supports no general one, and name what KMP's guarantee is bounding if not this text.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.