Exercises — Naive pattern matching — O(nm)

WHAT: count candidate starts. WHY: $P$ may only start where all $m$ of its characters still fit inside $T$ — beyond that it runs off the end. Here $n=6$, $m=3$. The formula from the parent note is $n-m+1=6-3+1=4$. The candidate shifts are $s=0,1,2,3$. WHAT IT LOOKS LIKE: look at figure below — the ruler XYZ can sit at 4 different starting positions before its right edge would poke past the end of XYZXYZ.

$j$ is the inner-loop counter — it walks across the pattern one letter at a time, $j=0,1,2,\dots$. "Fails at $j=2$" means: $P[0]$ matched $T[s]$, $P[1]$ matched $T[s+1]$, but $P[2]$ did not match $T[s+2]$. So two characters matched and the third broke the streak. We then stop (early break) and slide to $s+1$.

$n=18$, $m=4$, so shifts $s=0\dots 14$. Write out $T$ with indices: $\text{A A B A A C A A D A A B A A A B A A}$ $01234567891011121314151617$ At $s=0$: compare $P=$AABA against $T[\mathrm{0..3}]=$AABA. A=A, A=A, B=B, A=A → 4 comparisons, MATCH. So $s=0$ is valid. Walking the rest (mismatches stop early):

• $s=1$: ABAA vs AABA → A=A, B≠A, fail at $j=1$.
• $s=9$: $T[\mathrm{9..12}]=$AABA → MATCH.
• $s=12$: $T[\mathrm{12..15}]=$AAAB → A=A, A=A, A≠B, fail at $j=2$.
• $s=13$: $T[\mathrm{13..16}]=$AABA → MATCH.
• All other shifts fail on the first or second character. Valid shifts: $s=0,9,13$. Comparisons at $s=0$: $4$ (the full pattern, because it matched).

Candidates: $n-m+1=18-4+1=15$. Upper bound on comparisons: $(n-m+1)\cdot m=15\times 4=60$. This is the ceiling — the early break means the real count is usually far below it.

WHAT: hand-count every comparison. WHY: this exposes why "all-same-text + trailing mismatch" is the killer input. Candidate shifts: $n-m+1=5-3+1=3$, so $s=0,1,2$.

• $s=0$: AAB vs AAA → A=A (1), A=A (2), B≠A (3). Fails at $j=2$ after 3 comparisons.
• $s=1$: AAB vs AAA → 3 comparisons, fail.
• $s=2$: AAB vs AAA → 3 comparisons, fail. Total = $3+3+3=9$ comparisons. Note $9=(n-m+1)\cdot m=3\times 3$ — the bound is hit exactly. Why break never saves us early: every character of the text is A, so the first $m-1=2$ letters of $P$ always match; only the final B mismatches. The break fires on the last comparison, so we still pay full $m$ each shift.

Shifts: $9-4+1=6$. Each shift matches AAA then fails on the last B, costing the full $m=4$ comparisons. Total = $6\times 4=24$ comparisons — matching the parent note's figure. This is $\Theta (nm)$ made concrete.

WHAT: minimise total comparisons by choosing inputs. WHY: the outer loop always runs $n-m+1$ times (fixed); the only lever we control is the inner cost per shift. To make each shift cheap, force a mismatch on the very first comparison $j=0$ at every shift. Achieve this by making $P[0]$ a character that never appears in $T$. Example: $T=$ "AAAAAAA", $P=$ "BAA". At every shift, $T[s]=$A $\ne$ B $=P[0]$ → fails immediately after 1 comparison. Formula: total $=(n-m+1)\times 1=n-m+1$ comparisons, i.e. $O(n)$. WHAT IT LOOKS LIKE: the ruler slides all the way across but only ever peeks at its first letter each time — never spelling further.

Add a return s (or break on the outer loop) right after report match at s:

for s = 0 to n - m:
    j = 0
    while j < m and T[s+j] == P[j]:
        j = j + 1
    if j == m:
        return s        # stop at first match

Worst case for "match only at the end": the match sits at the last legal shift $s=n-m$. We must try all earlier shifts first. If each earlier shift costs up to $m$ comparisons and the final matching shift costs $m$: total $\le (n-m+1)\cdot m=O(nm)$ still. Stopping early helps only when the match is early; if the sole match is at the tail, we do essentially the full worst-case work anyway.

WHAT: maximise total comparisons under fixed $n,m$. WHY: the outer count $n-m+1=10$ is fixed; the adversary's only weapon is making every shift cost the full $m=3$. To cost $m$ at a shift, the first $m-1=2$ characters must match and the last must mismatch (a full-length near-miss). Choose $P=$ "AAB" and $T=$ "AAAAAAAAAAAA" (twelve As). At every shift AAB vs AAA: A=A, A=A, B≠A → 3 comparisons, and it never actually matches, so the outer loop never short-circuits. Maximum total $=(n-m+1)\cdot m=10\times 3=30$ comparisons. Proof it's optimal: no shift can ever cost more than $m$ comparisons (the inner loop is bounded by $m$), and there are only $n-m+1$ shifts. Hence total $\le (n-m+1)m=30$ for any input. Our construction attains $30$, so it is a maximiser. ∎

Shifts for both: $10-2+1=9$, so $s=0\dots 8$. Input X ($T=$ABABABABAB): at even $s$, AB=AB → 2 comparisons + MATCH. At odd $s$, $T[s]=$B$\ne$A → fail at $j=0$, 1 comparison. Even shifts $s=0,2,4,6,8$: five of them, each 2 comparisons = $10$. Odd shifts $s=1,3,5,7$: four of them, each 1 comparison = $4$. X total $=10+4=14$ comparisons (with 5 matches). Input Y ($T=$AAAAAAAAAA, $P=$AB): every shift → A=A (1), B≠A (2) → 2 comparisons, 0 matches. Y total $=9\times 2=18$ comparisons (with 0 matches). Conclusion: Y does more work ($18>14$) despite finding zero matches, while X finds five matches with less work. Why "many matches" ≠ "more work": cost is driven by how deep each comparison chain goes before stopping, not by whether it ends in a match. In X, odd shifts die instantly ($j=0$); in Y, every shift is forced to the last character. Depth of near-misses, not number of successes, sets the bill.