The simplest matcher tries every offset and compares until something fails. On the lab's opening text that costs 50 character comparisons against a proved bound of 123, and the gap between those two numbers is not a rounding error — it is the difference between a measurement of one input and a statement about all of them. This lesson establishes both numbers and what each is worth.
Core ideas
One hard idea: a count and a bound answer different questions. The other two say what one alignment costs and why ordinary text never spends it.
At offset i the matcher compares t[i] with p[0], then t[i+1] with p[1], and stops at the first disagreement. There are n − m + 1 offsets at which the pattern still fits, and the work at one of them is at least 1 comparison and at most m. Everything else on this page is those two facts multiplied out or measured.
The lab prints 50 for the text on screen. It prints 123 for every text of 43 characters searched for a pattern of 3. The first is evidence about one input and changes the moment a character is typed; the second is a theorem and does not. This Subject's whole hazard is reading the first as though it were the second, and every page here prints them side by side so that the substitution has to be made deliberately rather than by accident.
Over an alphabet of sigma equally likely letters, the chance that an alignment survives k comparisons is (1/sigma) to the power k, so the expected number of comparisons at one alignment sums to exactly sigma/(sigma − 1). At the thirteen distinct characters of the opening input that is 13/12, which is under 1.09 whatever m is. The bound multiplies by m; the expectation does not, and that single discrepancy is why the simplest matcher is the one most programs actually run.
The material
The algorithm, the bound with its proof, the measurement, and the expectation that explains why the two are so far apart.
Given a text t of length n and a pattern p of length m with m ≤ n, the naive matcher considers each offset i from 0 to n − m in turn. At offset i it compares t[i+k] with p[k] for k = 0, 1, 2, ..., stopping at the first k where they differ, or reporting a match at i when all m agree. The offsets it considers are called its alignments, and there are n − m + 1 of them.
Nothing is remembered between alignments. That is the whole of the algorithm and also the whole of the criticism of it: after an alignment has matched five characters and failed on the sixth, the matcher throws those five away and starts the next offset from nothing. The rest of this module is three different things to do with the information that was thrown away.
On any text of length n and any pattern of length m, the naive matcher makes at most m(n − m + 1) character comparisons, and at least n − m + 1.
There are exactly n − m + 1 alignments, because i runs over the integers from 0 to n − m inclusive and the loop body is entered once for each.
At one alignment the inner loop increments k from 0 and stops the first time t[i+k] differs from p[k], or when k reaches m. Each iteration performs one comparison and k never exceeds m, so one alignment costs at most m comparisons; and the loop body runs at least once, so it costs at least 1. Multiplying both ends by the number of alignments gives the two bounds.
Both are attained. The lower one is reached whenever no character of the text equals p[0]; the upper one needs every alignment to match m − 1 characters and then fail, which is the input the sibling lesson “The Text Built to Reach the Bound” constructs.
□
The lab opens on the text the rain in spain stays mainly in the plain and the pattern ain, so n = 43, m = 3 and there are 41 alignments. Five of those offsets carry an a: 5, 14, 20, 25 and 40. The other 36 disagree on the very first comparison and cost 1 each. Offset 20 matches the a of stays and then fails on y, costing 2. The remaining four are matches and cost 3 each. So the total is 36 + 2 + 12 = 50, and the panel reports 50.
The bound over the same input is 3 × 41 = 123. The measurement is 50, which is 123/50 = 2.46 times smaller, and both numbers are right. Change one character of the text and 50 moves; 123 does not move until the lengths do.
If each character of the text is drawn independently and uniformly from an alphabet of sigma ≥ 2 letters, the expected number of comparisons the naive matcher makes at one alignment is at most sigma/(sigma − 1).
The alignment performs a comparison for k = 0, and performs the comparison at k only if the first k agreed, which for independent uniform characters has probability (1/sigma) to the power k.
So the expected count is the sum over k ≥ 0 of (1/sigma)^k, a geometric series with ratio 1/sigma < 1, which is exactly 1/(1 − 1/sigma) = sigma/(sigma − 1). Truncating the series at m terms, as the real algorithm does, can only reduce it.
The quantity m does not appear. A longer pattern gives more ways to fail early, not more work per alignment, and that is the whole reason the naive matcher is linear in practice.
□
At sigma = 13, the thirteen distinct characters of the opening input, the expectation is 13/12, just over 1.08. The measured figure is 50/41, just over 1.22. The two disagree because the text is English rather than uniform — the letter a is commoner than a thirteenth of the text — and the panel prints both rather than picking one.
The first table under the chart repeats your text 1 to 6 times with the pattern unchanged. On the opening input the counts come out 50, 102, 154, 206, 258 and 310 as n runs 43, 86, 129, 172, 215, 258. The differences are 52 every time: that is a straight line, not a parabola.
It has to be. Holding m fixed makes the bound m(n − m + 1) linear in n as well, so nothing in that table can be quadratic in anything. The column worth reading is comparisons per character, which moves only from 1.16 to 1.20 across the six rows. The quadratic needs m to grow with n, which the second table does and this one deliberately does not.
The panel also runs Knuth–Morris–Pratt and Horspool over whatever you typed, so that the comparison is on one input rather than between two anecdotes. On the opening text they take 44 and 25 against naive's 50. Horspool is ahead because it skips; KMP is behind by 6 because it reads every character of the text once and naive mostly reads one character per alignment and leaves.
All three report the same 4 matches, at offsets 5, 14, 25 and 40, and the panel checks all three against a scan that compares the whole substring at every offset. That check is not ceremony: a matcher that shifts too far returns a shorter list of positions, and a shorter list of correct positions is the one kind of wrong answer that looks exactly like a right one.
Interactive
Comparisons measured per alignment, against m and against m(n − m + 1)
Method
Write the measurement and the bound in two columns from the start, and never let a sentence use one where it means the other.
n − m + 1 is fixed by the two lengths and nothing about the characters can change it. It is the denominator of every per-alignment figure on the page, and getting it wrong by one is the commonest arithmetic slip in this module.
On ordinary text almost all of them fail on the first comparison. Counting how many start with p[0] gives the total almost immediately: everything else costs 1, and only those few cost more.
m(n − m + 1) is a separate calculation from the same two lengths, and it must be written down even when it is five times too big. A page that prints only the measurement has said nothing about any text but the one on screen.
Retyping the text moves the count and leaves the bound alone if the lengths hold. Lengthening the pattern moves both. Any sentence that survives only one of those two edits is a sentence about that input.
The text is the rain in spain stays mainly in the plain and the pattern is ain. Offsets are counted from 0, so n = 43, m = 3, and the alignments run from 0 to 40.
The single most useful line in that table is the first. Thirty-six of the forty-one alignments never reach a second comparison, and that is the whole reason the measured figure sits at 1.22 per alignment rather than at 3.
Now predict before you check. Replace the pattern with in and the answer changes in two places at once: there are 42 alignments rather than 41, and i is a commoner first character than a, so more alignments survive to a second comparison. The supplied first move is the bound — it becomes 2 × 42 = 84, which is smaller than 123 even though the pattern got easier to find. Say why a shorter pattern lowers the bound and then say whether it must lower the count.
For a second rehearsal, keep ain and delete the final word of the text. Two matches survive, the alignment count falls by 6, and the count falls by more than 6. Say by exactly how much before running it, using nothing but the breakdown above.
You should be able to count the alignments from the two lengths, break the comparison total down by where each alignment died, compute m(n − m + 1) beside it, explain why m appears in the bound and not in the expectation, and say what a table that repeats one text can and cannot demonstrate.
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.