Lesson · Strings and Pattern Matching · Matching one pattern

The Text Built to Reach the Bound

A run of twenty-four a's searched for aaaab costs 100 comparisons against a bound of 100. That is the worst case attained, not approached. But repeating that same text 1 to 6 times still gives a straight line, because holding m fixed makes the bound linear too — the quadratic needs a family in which m grows with n, and the lab builds one where the count is m(m − 1) and equals the bound in every row.

Open the interactive lesson Practice

text a^24, pattern aaaab: every alignment matches m − 1 then fails measured 100 = m(n − m + 1) = 5 × 20 = 100, the bound attained repeating that text: 100, 220, 340, 460, 580, 700 - a straight line the family: text a^(2(m − 1)), pattern a^(m − 1) b there the count is m(m − 1), equals the bound, and per character is m/2 KMP on the same family is 3(m − 1), so 1.5 per character, flat

The bound attained on one text, and the family where it grows without limit

Core ideas

What this lesson establishes

The hard idea is the one the lab's author retracted after printing the numbers: a fixed pattern cannot exhibit a quadratic. The other two are the construction and what makes it worst.

The worst case is constructed, not encountered

For every alignment to cost the full m, each one must agree on m − 1 characters and disagree on the last. A run of one letter with a pattern that is that letter m − 1 times followed by a different one does exactly that at every offset. The lab opens on aaaaaaaaaaaaaaaaaaaaaaaa and aaaab: 20 alignments, 5 comparisons each, 100 in total, and the bound 5 × 20 is 100 as well. The measured column and the proved column agree for the first and only time on this course.

Repeating a text with the pattern fixed cannot show a quadratic

Concatenate the adversarial text with itself and the counts read 100, 220, 340, 460, 580, 700 — differences of 120, a line. That is forced: with m held at 5 the bound m(n − m + 1) is itself linear in n, so nothing in that table can be quadratic in anything. A page that showed those six numbers and said “quadratic” would be reading steep growth as a different order of growth, and steepness is a constant.

The quadratic is a statement about a family in which m grows with n

Take the text to be 2(m − 1) copies of a and the pattern to be m − 1 copies followed by b. Then the alignment count is m − 1, each alignment costs m, and the total is m(m − 1), which is the bound. As m runs 3 to 11 the lab prints 6, 12, 20, 30, 42, 56, 72, 90, 110, and the comparisons per character are exactly m/2 — rising without limit. Knuth–Morris–Pratt on the same family makes 3(m − 1) comparisons, which is 1.5 per character in every row.

The material

Attaining the bound, and then earning the word quadratic

The construction and its proof, the table that cannot show what it looks like it shows, and the family that can.

Definition · The adversarial pair

For a letter a and a different letter b, write a^k for the string of k copies of a. The adversarial pair at pattern length m is the text a^N for some N ≥ m together with the pattern a^(m − 1) b. Every character of the text is a; the pattern agrees with the text on its first m − 1 characters at every offset and disagrees on its last.

Theorem · The adversarial pair attains the bound

On the text a^N with the pattern a^(m − 1) b, the naive matcher makes exactly m(N − m + 1) comparisons and reports no match — which is the maximum possible for those two lengths.

Fix an alignment at offset i, which exists for 0 ≤ i ≤ N − m. For k < m − 1 the comparison of t[i+k] with p[k] is a against a and succeeds, so the inner loop reaches k = m − 1.

At k = m − 1 the comparison is t[i+m−1] = a against p[m−1] = b, which fails. So the alignment makes exactly m comparisons and reports nothing.

There are N − m + 1 alignments, each costing m, so the total is m(N − m + 1). That is the upper bound proved on the opening page of this module, so it is attained and cannot be improved.

□

At N = 24 and m = 5 this is 5 × 20 = 100, and the panel's status line says so in the strongest terms it has: the measured count IS the bound. No other preset in this kit produces that sentence.

The table that looks like a quadratic and is not one

The first table repeats whatever is in the box 1 to 6 times with the pattern unchanged. On the adversarial text it reads 100, 220, 340, 460, 580, 700 at n = 24, 48, 72, 96, 120, 144. Those differences are 120 each and the comparisons per character creep from 4.17 to 4.86. It is a line with a steep slope.

Theorem · A fixed pattern makes the bound linear

With m held constant, m(n − m + 1) is a linear function of n, and the naive matcher's count is at most that. So no family of inputs with a fixed pattern can make the comparison count grow faster than linearly in n.

This is the claim the kit's author withdrew after printing the numbers, and the docstring records the withdrawal. It is worth being precise about what was wrong: nothing in the six counts was mismeasured, and the growth really is much steeper than on English text. What was wrong was the word. Four and a half comparisons per character is a constant, and a constant times n is not quadratic however large the constant is.

The family where m grows with n

The second table is fixed rather than read from the boxes, because a text that reaches the bound has to be built and cannot be typed by accident. At each m from 3 to 11 it takes the text a^(2(m − 1)) and the pattern a^(m − 1) b, so n = 2(m − 1) and the pattern is half the text.

m n naive m(n - m + 1) per character KMP 3 4 6 6 3/2 6 5 8 20 20 5/2 12 7 12 42 42 7/2 18 9 16 72 72 9/2 24 11 20 110 110 11/2 30

Read the arithmetic rather than the shape. The alignment count is n − m + 1 = 2(m − 1) − m + 1 = m − 1, each alignment costs m, so the total is m(m − 1) and equals the bound in every row. Per character that is m(m − 1)/(2(m − 1)) = m/2, which grows without limit as the family is extended. KMP's column is 3(m − 1), which is 1.5n: flat per character, in every row, for ever.

That is the honest form of the quadratic claim. It is not “naive matching is quadratic”, which is about an algorithm and is false on almost every input anyone types. It is “there is a family of inputs on which naive matching's count is a constant times the product of the two lengths, and that family is exhibited here”. The lower table is the exhibit and the upper table is not.

Horspool, for contrast, is at its best here

The third matcher takes 20 comparisons on the opening text, five times fewer than naive's 100, and m − 1 in every row of the family table. Its shift table sends it forward by 1 each time, but it compares the window from the right, so it meets the b first and fails immediately. The sibling lesson “The Text Where Nothing Is Skipped” reverses the pattern's letters and gets 130 comparisons on 30 characters, which is the same algorithm at its worst on almost the same text.

Interactive

Naive matching, and the two texts that answer differently

Comparisons measured per alignment, against m and against m(n − m + 1)

The input where the measurement and the bound are the same number

The bar chart is a solid block sitting on the dashed line, because every alignment costs the full m. Read the two tables as answering different questions: the upper one grows the text with the pattern fixed and is linear by construction, and the lower one grows the pattern with it and is the only place on this page where the quadratic appears.

Worked example

The text

The pattern

Show the alignment at1

Alignments tried—

Characters compared—

Per alignment, measured—

Per alignment, uniform alphabet—

The proved bound m(n − m + 1)—

Matches, and matches by definition—

KMP on the same text—

Horspool on the same text—

Type any text and any pattern. The bar chart is one bar per alignment and its height is the characters compared there, so a text of mostly first-character mismatches is a flat chart and the adversarial text is a solid block at the line. The first table repeats your text 1 to 6 times with the pattern unchanged, which grows n and holds m: the count then has to be linear in n, and the column that matters is comparisons per character. The second table grows m as well, and that is where the quadratic lives.

Method

Building a worst case, and naming its growth honestly

Construct the input from the bound rather than searching for it, then check which quantity you actually varied.

Read the bound backwards to get the input

m(n − m + 1) is attained when every alignment costs m, which means every alignment matches m − 1 characters and fails on the last. Writing a text and pattern with that property is then mechanical rather than inventive.

Check that the failure really is at the last position

A run of a's with the pattern baaaa also has 26 alignments, but each fails on the first comparison and the total is 26, not 130. Where the odd character sits in the pattern decides everything, and for the left-to-right matcher it has to sit at the end.

Name which quantity you varied before using the word quadratic

If the pattern is fixed, the bound is linear and so is anything under it. A quadratic claim is a claim about a family in which both lengths move together, and it needs a row for each member of the family.

Read the per-character column, not the total

Totals rise in both tables and that is uninformative. Comparisons per character is 4.17 rising to 4.86 in the upper table, which is a constant settling down, and m/2 in the lower one, which is not.

Put a second algorithm in the same table

KMP's column is what makes the lower table an argument rather than an observation: m(m − 1) beside 3(m − 1) on the same inputs is the difference between an unbounded ratio and a fixed one.

Attaining a bound, and what growth means

Score 0 / 0

Choose the answer you can justify.

One hundred comparisons, and then the family that leaves it behind

The text is twenty-four a's and the pattern is aaaab, so n = 24, m = 5, and the alignments run from 0 to 19.

alignments n - m + 1 = 24 - 5 + 1 = 20 cost of one alignment 4 matches on 'a', 1 fail on 'b' = 5 measured total 20 x 5 = 100 the bound m(n - m + 1) = 5 x 20 = 100 measured / bound = 1 repeat the text 1..6 times, pattern fixed: n 24 48 72 96 120 144 cmp 100 220 340 460 580 700 differences 120: a line the family, m growing with n: n = 2(m - 1) m 3 5 7 9 11 cmp 6 20 42 72 110 = m(m - 1), = the bound /char 3/2 5/2 7/2 9/2 11/2 = m/2, unbounded KMP 6 12 18 24 30 = 3(m - 1), = 1.5n, flat

The two blocks at the bottom are the same algorithm on inputs of the same kind, and only the second earns the word quadratic. If you cover the m row of the third block, the counts 6, 20, 42, 72, 110 look like nothing in particular; it is the fact that n is tied to m that makes them n^2/4 in disguise.

For a faded rehearsal, work out what the family looks like at m = 13. The supplied first move is n = 2(m − 1) = 24, which is the same length as the opening text. Give the naive count, the bound, the per-character figure and KMP's count, then check them against the lab by extending the family in your head rather than on screen — the table stops at 11.

Then do the harder one. Keep m = 5 and ask what text of length 24 makes naive matching cost as little as possible. The answer is not unique and the minimum is 20, one comparison per alignment; say which texts achieve it, and notice that the bound is 100 for every one of them.

Common mistakes

Calling a steep line a quadraticFour and a half comparisons per character is a large constant and constants do not change the order of growth. The test is whether the per-character figure keeps rising: in the upper table it settles near 4.86, in the lower one it is m/2 and has no ceiling.

Believing the worst case is rare because it looks contrivedIt is contrived, and it is also exactly what a periodic input looks like — runs of one symbol, or a short cycle repeated, which is what DNA, binary sensor traces and padded records are made of. “Unlikely for English prose” is a claim about a distribution of inputs, and it is not a claim the bound makes or needs.

Reading m(n − m + 1) as nmThey differ by m(m − 1), which is 20 on the opening text and 110 at the bottom of the family table, where nm is 220 and the true bound is 110 — a factor of two. The looser form is usually harmless as an order of growth and is wrong as a number, and this page is about the number.

Check your understanding

✓

Finish when you can construct a worst-case input for any m and say exactly which table earns the word quadratic.

You should be able to build the adversarial pair from the bound rather than recall it, prove that it attains m(n − m + 1), explain why a fixed pattern forces linear growth, derive m(m − 1) and m/2 for the family, and say what KMP's flat 1.5 per character means beside it.

Note: This closes the naive matcher. Everything in the rest of the course is an answer to the same question: what to do with the m − 1 characters this algorithm matched and threw away. “Borders, and the Failure Function Built” keeps them by remembering how much of the pattern is still aligned; “Shifting by More Than One” jumps past positions no match can start at; and “A Rolling Hash, and a Collision You Can Read” stops comparing characters altogether.