Lesson · Strings and Pattern Matching · Skipping, and its worst case

The Text Where Nothing Is Skipped

Put the pattern's odd character at the front instead of the end and Horspool's table becomes useless: the window's last character always matches, the shift is always 1, and each alignment compares m characters before failing. The lab reports 130 comparisons against the naive matcher's 26 on the same input — exactly five times — and reversing the pattern reverses the two numbers. The algorithm did not change; the position of one character did.

Open the interactive lesson Practice

text a^30, pattern baaaa: 26 alignments, 0 skipped, every shift 1 each alignment matches m − 1 from the right, then fails on the b measured: Horspool 130, naive 26, KMP 30, on one 30-character text 130 = 26 × 5 = the alignments times m: the bound m(n − m + 1), attained reverse the pattern to aaaab: Horspool 26 and naive 130, exactly swapped Horspool has no better worst case than naive matching, only a better average

The same table, the same text, and one character in a different place

Core ideas

What this lesson establishes

The hard idea is that both worst cases are the same bound reached by opposite inputs. The other two are why this text defeats the table and what survives it.

The table is useless when the window's last character is always in the pattern

The pattern is baaaa and the table is built from baaa, so a → 1 and b → 4. Every window of a run of a's ends in a, so every shift is 1 and the window advances as slowly as the naive matcher's. The panel reports 26 alignments out of 26 examined and 0 alignments skipped, which is the only preset in this kit that prints a zero there.

Comparing from the right is what turns a slow shift into expensive alignments

At each alignment the comparison runs p[4], p[3], p[2], p[1] — four a's against four a's, all matching — and then p[0] = b against a, which fails. So one alignment costs the full m = 5, and 26 alignments cost 130. The naive matcher on the same input compares p[0] = b first at every alignment and leaves after one comparison, for 26 in total. The direction of comparison is the whole difference.

The two worst cases are the same bound, reached by mirror-image inputs

Reverse the pattern to aaaab on the same text and the numbers swap exactly: Horspool 26, naive 130. Both algorithms have worst case m(n − m + 1), which is 5 × 26 = 130 here, and both attain it — on different inputs. Neither algorithm dominates the other and neither has a guarantee the other lacks; Horspool's advantage is an average over texts, and an average over texts is not a statement any single measurement can make.

The material

One character moved, and a factor of five in the other direction

Why the shift collapses, why the alignments become expensive, the mirror input, and what remains true of both algorithms.

Keep the text as a run of thirty a's and set the pattern to baaaa. The shift table is built from baaa, giving a → 1 and b → 4; every character of the text is a; so every shift is 1 and the window visits all 26 alignments in turn. Nothing is skipped.

Theorem · Horspool attains m(n − m + 1) on this family

On the text a^N with the pattern b a^(m−1), Horspool examines all N − m + 1 alignments, makes exactly m comparisons at each, and reports no match. Its total is m(N − m + 1), which is the maximum possible.

The shift table built from p[0..m−2] = b a^(m−2) gives shift[a] = 1, because a occurs at index m − 2, the largest index below m − 1. Every character of the text is a, so every shift is 1 and every offset from 0 to N − m is examined.

At one alignment the comparison runs from k = m − 1 downwards. For k ≥ 1 the pattern character is a and the text character is a, so those m − 1 comparisons succeed. At k = 0 the pattern character is b and the text character is a, so the comparison fails. That is m comparisons and no match.

Multiplying gives m(N − m + 1), and the same bound proved for the naive matcher applies here for the same reason: N − m + 1 alignments at m comparisons each is the ceiling for any algorithm that compares within a window and shifts by at least 1.

□

At N = 30 and m = 5 that is 5 × 26 = 130, and the panel says so: 130 comparisons over 26 alignments, 0 skipped, average shift exactly 1. The naive matcher on the same input makes 26 and KMP makes 30.

Example · The mirror image, one keystroke away

Change the pattern to aaaab and keep the thirty a's. Now the table is built from aaaa, still giving a → 1, so Horspool still examines all 26 alignments and still skips nothing — but the comparison from the right meets p[4] = b against a immediately and fails after one comparison. Horspool makes 26 and the naive matcher, which matches four a's before reaching the b, makes 130. The two counts have swapped and neither algorithm was touched.

text a^30, m = 5, 26 alignments Horspool naive KMP pattern baaaa odd character at the front 130 26 30 pattern aaaab odd character at the end 26 130 56 pattern aaaaa no odd character, 26 matches 130 130 30 the bound m(n - m + 1) = 5 x 26 for both 130 130

The third row is the one that spoils any story about one algorithm being for one kind of input. A pattern of five a's matches at every one of the 26 alignments, so both algorithms compare all five characters at all 26 offsets and both make 130. The bound is attained by both, simultaneously, and KMP makes 30.

What Horspool's guarantee actually is

It is m(n − m + 1), and that is the same as the naive matcher's. There is no theorem of the form “Horspool is never worse than naive matching” — this page is a counterexample to it — and no theorem bounding Horspool below the naive matcher's worst case. What is true is a statement about an average: over texts whose characters are drawn independently and uniformly from a large alphabet, the expected number of comparisons is close to n/m.

That expectation is where the reputation comes from, and it is worth being clear about what kind of claim it is. It quantifies over a distribution of inputs, not over inputs, so a single text can be arbitrarily far from it in either direction and nothing is refuted. This page's text is one such, and the previous page's prose is another in the opposite direction.

Which of the four matchers is safe on a text like this

KMP makes 30 comparisons on the run of thirty a's with baaaa, and 56 with aaaab, both under 2n = 60. The automaton takes exactly 30 steps on either. Those two are the ones whose counts cannot be made to blow up by choosing the text, because their bounds are linear in n with no m in them at all.

So the ranking across this course's four matchers changes three times depending on the input, and the two bounds do not change at all: m(n − m + 1) for naive matching and Horspool, 2n for KMP, exactly n for the automaton. When the question is which to use on text you have not seen, the bounds are the only evidence available.

Interactive

Shifting by more than one, and the text that stops it

Characters skipped and comparisons made, against naive matching and KMP

The input where every shift is one, and the counter that says so

The bar chart is a solid block at the dashed line because every alignment costs the full m, and the counter for characters skipped reads 0 — the only preset here that does. Reverse the pattern in the box to aaaab and watch the Horspool and naive columns exchange values.

Worked example

The text

The pattern

Show the alignment at1

Alignments examined—

Alignments naive would try—

Characters compared—

Characters skipped entirely—

Average shift—

Comparisons, naive—

Comparisons, KMP—

Matches, and matches by definition—

Horspool compares the window right to left and then shifts by the last occurrence of the text character under the window's last position, looked up in a table built from the pattern's first m − 1 characters. A character the pattern does not contain at all shifts the full m. The saving comes from the TEXT as much as from the pattern: pick the third worked example, where the last character of every window matches and the shift is always 1.

Method

Finding an algorithm's worst case by asking what its rule needs

Read the shift rule and the comparison order as two separate requirements, then defeat each one.

Defeat the shift first: make the window's last character common in the pattern

shift[c] is small when c occurs late in p[0..m−2]. A pattern whose penultimate character is the text's only character forces shift = 1 at every alignment, which is the most any input can do to the table.

Then make each alignment expensive, using the comparison order

Horspool compares from the right, so the disagreement must be as far left as possible: put the one character the text lacks at p[0]. Both requirements together give b a^(m−1) against a^N.

Reverse the pattern and check the numbers swap

If the construction is right, moving the odd character from the front to the end should transfer the 130 to the naive matcher. That the swap is exact is the evidence that the worst case is about the comparison order and nothing else.

Read both bounds before choosing an algorithm

m(n − m + 1) is 130 here and 2n is 60. On a text nobody has typed yet those two numbers are the whole of what is known, and the measured columns from the previous page are not evidence about this one.

Worst cases, mirror images, and what a bound covers

Score 0 / 0

Choose the answer you can justify.

One hundred and thirty comparisons, and the same input the other way round

The text is thirty a's. The pattern is baaaa, so m = 5, the shift table is built from baaa, and there are 26 alignments.

shift table a -> 1 (a occurs at index 3) b -> 4 one alignment, compared from the right: k = 4 p[4] = a vs a match k = 3 p[3] = a vs a match k = 2 p[2] = a vs a match k = 1 p[1] = a vs a match k = 0 p[0] = b vs a FAIL 5 comparisons window's last character is a, so shift = 1 alignments examined n - m + 1 = 30 - 5 + 1 = 26 comparisons 26 x 5 = 130 alignments skipped = 0 average shift = 1 the bound m(n - m + 1) 5 x 26 = 130 naive on the same input fails on p[0] at once, 26 x 1 = 26 KMP on the same input = 30 reverse the pattern to aaaab: Horspool 26, naive 130

The line to read twice is the last. Reversing the pattern changes neither algorithm, neither bound, nor the text, and it exchanges the two measured counts exactly. Any sentence of the form “this algorithm is faster” that survives that keystroke was not about the measurement.

For a faded rehearsal, keep the text and set the pattern to abaaa. The supplied first move: the table is built from abaa, so a → 1 and b → 3, and the shift is still 1 at every alignment because the text is all a's. Work out the cost of one alignment by comparing from the right, give the total, and say whether it is nearer 26 or nearer 130.

Then do the harder one. Find a pattern of length 5 over {a, b} on which Horspool and the naive matcher make the SAME number of comparisons on thirty a's. The supplied hint: there is one where both make 130, and it has no b in it at all. Say why, and say what that says about the claim that skipping helps.

Common mistakes

Calling this input unrealistic and moving onA run of one symbol is what padded fixed-width records, silence in an audio stream, and a zeroed disk block look like, and a short repeated cycle is what DNA and instruction streams look like. But the more important point is that realistic is a claim about a distribution and the bound is not: the bound covers this input because it covers every input, which is the only reason it is worth having.

Concluding that Horspool should compare left to rightIt cannot. The shift rule needs a known character at a known offset to look up, and comparing from the right is what makes the window's last character the one whose identity is always established. A left-to-right variant has no table to consult and is the naive matcher.

Reading 130 against 26 as a five-fold slowdown of the algorithmIt is a five-fold slowdown on one input, and the reversed pattern is a five-fold speed-up on the same text. The factor is a property of the pair, and averaging the two would produce a number describing neither.

Check your understanding

✓

Finish when you can construct Horspool's worst case from its two rules and predict the reversal without running it.

You should be able to say which rule forces shift = 1 and which forces m comparisons per alignment, prove the total is m(n − m + 1), predict that reversing the pattern swaps the two counts, explain why aaaaa makes both algorithms attain the bound at once, and state what kind of claim n/m is.

Note: Every matcher so far compares characters, and three of the four can be made expensive by choosing them. The next module stops comparing: “A Rolling Hash, and a Collision You Can Read” reduces a window to one number and compares numbers instead — which introduces a new failure that none of these pages has, because two different windows can share a number.