Naive pattern matching — O(nm): Worked examples

Two things we will count in every example:

Shift $s$ — the starting index in the text where we lay the pattern down. Think of it as "how many steps right have we slid the transparent ruler?"
Character comparisons — one comparison is checking a single letter $T [s + j]$ against $P [j]$ . This is the unit the $O (nm)$ cost is measured in.

The scenario matrix

Every input to a pattern matcher falls into one of these case classes. Our worked examples below are labelled with the cell they hit, and together they touch every row.

#	Case class	What makes it special	Covered by
A	Match in the middle	ordinary case, break fires early on misses	Ex 1
B	Match at the very start ( $s = 0$ )	left edge, no sliding needed to find first hit	Ex 1
C	Match at the very end ( $s = n - m$ )	right edge — pattern touches the last char	Ex 2
D	No match at all	inner loop never reaches $j = m$	Ex 3
E	Overlapping matches	matches whose regions share characters	Ex 4
F	Degenerate: $m = 1$	pattern is a single character	Ex 5
G	Degenerate: $m = n$	pattern as long as text — one shift only	Ex 6
H	Empty pattern ( $m = 0$ )	limiting/boundary input	Ex 6
I	Worst case $Θ (nm)$	early break never helps	Ex 7
J	Best/expected case	mismatch on char 0 every time → $\approx O (n)$	Ex 8
K	Real-world word problem	DNA / text search framing	Ex 9
L	Exam twist — count comparisons exactly	reason about cost, not just position	Ex 10

Example 1 — middle + start matches (cells A, B)

Here $n = 8$ , $m = 3$ , so shifts run $s = 0 \dots n - m = 5$ .

$s = 0$ : compare $T [0] T [1] T [2] =$ "ABC" with "ABC" → A=A, B=B, C=C. All 3 match, $j$ reaches $m = 3$ . MATCH at $s = 0$ (cell B, left edge). Why this step? We start $j = 0$ and walk the pattern; only when $j == m$ do we declare success.
$s = 1$ : $T [1] =$ "B" vs $P [0] =$ "A" → mismatch at $j = 0$ . Break immediately. One comparison spent. Why this step? The early break kills the shift the instant a letter disagrees — no point checking "C" or "A" after.
$s = 2$ : $T [2] =$ "C" vs "A" → mismatch. Break.
$s = 3$ : $T [3] T [4] T [5] =$ "ABC" → match. MATCH at $s = 3$ (cell A, middle).
$s = 4$ : $T [4] =$ "B" vs "A" → mismatch. Break.
$s = 5$ : $T [5] T [6] T [7] =$ "CAB" → C vs A mismatch. Break.

Answer: matches at $s = 0, 3$ .

Example 2 — match at the very end (cell C)

$n = 9$ , $m = 3$ , shifts $s = 0 \dots 6$ .

$s = 0 \dots 5$ : the first letters "X","Y","Z","X","Y","Q" all differ from $P [0] =$ "P" except we must check each. At $s = 5$ , $T [5] =$ "Q" vs "P" → mismatch. Every one of these breaks on the first char. Why this step? $P$ begins with "P", which appears in $T$ only near the end, so all early shifts die at $j = 0$ .
$s = 6$ : $T [6] T [7] T [8] =$ "PQR" vs "PQR" → P=P, Q=Q, R=R. MATCH at $s = 6$ . Why this step? $s = 6 = n - m$ is the last legal shift; the pattern's final char $P [2]$ lands on $T [8]$ , the last character of the text. Any larger $s$ would run off the end.

Answer: single match at $s = 6 = n - m$ .

Example 3 — no match anywhere (cell D)

$n = 5$ , $m = 5$ ? No — "WORLD" has length 5 and "HELLO" length 5, so $m = n$ . Shifts $s = 0 \dots n - m = 0$ : only one candidate.

$s = 0$ : $T [0] =$ "H" vs $P [0] =$ "W" → mismatch at $j = 0$ . Break. Why this step? With $m = n$ there's exactly one place to check, and the very first letter fails.
Inner loop never reached $j = m$ , so no shift is reported.

Answer: no matches — empty result. Exactly 1 comparison was made.

Example 4 — overlapping matches (cell E)

$n = 4$ , $m = 2$ , shifts $s = 0 \dots 2$ .

$s = 0$ : $T [0] T [1] =$ "AA" → match. MATCH at $s = 0$ .
$s = 1$ : $T [1] T [2] =$ "AA" → match. MATCH at $s = 1$ . Why this step? $s = 0$ used characters at indices $0, 1$ ; $s = 1$ uses indices $1, 2$ . Index 1 is shared — the two matches overlap. Naive matching happily reports both because it treats each shift independently.
$s = 2$ : $T [2] T [3] =$ "AA" → match. MATCH at $s = 2$ .

Answer: matches at $s = 0, 1, 2$ — three overlapping occurrences.

Example 5 — degenerate: single-character pattern (cell F)

$n = 6$ , $m = 1$ , shifts $s = 0 \dots 5$ (that's $n - m + 1 = 6$ shifts — one per character).

Each shift compares exactly one character: $T [s]$ vs "A". Why this step? When $m = 1$ the inner loop runs at most once, so "does this shift match?" collapses to "is this letter an A?"
Letters of "BANANA" by index: B(0), A(1), N(2), A(3), N(4), A(5). Matches where the letter is "A": $s = 1, 3, 5$ .

Answer: matches at $s = 1, 3, 5$ .

Recall Why

$m = 1$ makes cost exactly $O (n)$ Every shift does $\leq m = 1$ comparison, and there are $n - m + 1 = n$ shifts, so total comparisons $= n$ . The $O (nm)$ bound becomes $O (n \cdot 1) = O (n)$ — the search degenerates into a linear scan. ✔

Example 6 — degenerate lengths: $m = n$ and empty pattern (cells G, H)

(a) $m = n = 4$ : shifts $s = 0 \dots n - m = 0$ → only one shift.

$s = 0$ : compare all 4 chars C=C, O=O, D=D, E=E → match. MATCH at $s = 0$ . Why this step? When the pattern is as long as the text there's literally nowhere to slide; you check the single alignment and stop.

(b) $m = 0$ (empty pattern): shifts $s = 0 \dots n - m = 0 \dots 4$ → $n - m + 1 = 5$ shifts.

The inner loop condition j < m is j < 0, false immediately, so it runs zero comparisons and j==m (both $0$ ) is instantly true. Why this step? An empty string is a substring of every position, including one past the last character. So the empty pattern "matches" at all $n + 1 = 5$ positions $0, 1, 2, 3, 4$ .

Answers: (a) match at $s = 0$ . (b) matches at $s = 0, 1, 2, 3, 4$ (five positions).

Example 7 — the worst case $Θ (nm)$ (cell I)

$n = 6$ , $m = 3$ , shifts $s = 0 \dots 3$ → 4 shifts.

Every shift: $T [s] =$ "A"= $P [0]$ ="A" ✓, $T [s + 1] =$ "A"= $P [1]$ ="A" ✓, then $T [s + 2] =$ "A" vs $P [2] =$ "B" ✗. Why this step? The first $m - 1 = 2$ characters always match (all A's), so the break only fires on the last comparison. We pay the maximum $m = 3$ comparisons per shift.
Total $= (n - m + 1) \times m = 4 \times 3 = 12$ comparisons. Why this step? This is exactly the product in the $O (nm)$ formula reached with no early exit — the algorithm's ceiling.

Answer: 12 comparisons; zero matches. This is where naive matching earns its $Θ (nm)$ reputation, motivating KMP Algorithm and Boyer-Moore Algorithm.

Example 8 — best / expected case (cell J)

$n = 6$ , $m = 2$ , shifts $s = 0 \dots 4$ → 5 shifts.

Every shift: $T [s]$ vs $P [0] =$ "X" → mismatch immediately (no letter of "ABCDEF" is "X"). Break after 1 comparison. Why this step? When the first pattern character is rare/absent, the break fires at $j = 0$ every time — the inner loop never gets going.
Total $= (n - m + 1) \times 1 = 5$ comparisons.

Answer: 5 comparisons, no matches — this is the $\approx O (n)$ behaviour that makes naive matching perfectly fine on typical text. Contrast with Ex 7's 12: same-ish sizes, wildly different cost.

Example 9 — real-world word problem: DNA search (cell K)

$n = 14$ , $m = 7$ , shifts $s = 0 \dots 7$ .

$s = 0$ : $T [0..6] =$ "GATTACA" $= P$ → MATCH. 7 comparisons (full pattern). Why this step? A successful shift always spends the full $m$ comparisons — it must confirm every letter.
$s = 1$ : $T [1] =$ "A" vs $P [0] =$ "G" → mismatch, break after 1.
$s = 2..6$ : each first letter ("T","T","A","C","A") differs from "G" → break after 1 comparison each.
$s = 7$ : $T [7..13] =$ "GATTACA" $= P$ → MATCH. 7 comparisons. Why this step? The second copy begins exactly at index 7; the two matches are non-overlapping because they abut ( $s = 0$ covers $0..6$ , $s = 7$ covers $7..13$ ).

Answer: motif found at $s = 0$ and $s = 7$ ; two non-overlapping occurrences. Total comparisons $= 7 + 1 + 1 + 1 + 1 + 1 + 7 =$ wait — count them: successes $2 \times 7 = 14$ , plus failures at $s = 1, 2, 3, 4, 5, 6$ = 6 single comparisons → $14 + 6 = 20$ .

Example 10 — exam twist: count comparisons exactly (cell L)

$n = 4$ , $m = 2$ , shifts $s = 0 \dots 2$ → 3 shifts.

$s = 0$ : $T [0] T [1] =$ "AB"="AB" → match. Comparisons: A=A ✓, B=B ✓ → 2 comparisons.
$s = 1$ : $T [1] =$ "B" vs $P [0] =$ "A" → mismatch. 1 comparison. Why this step? Break after the first letter; we never look at $T [2]$ for this shift.
$s = 2$ : $T [2] T [3] =$ "AB"="AB" → match. 2 comparisons.

Answer: (a) matches at $s = 0, 2$ . (b) total $= 2 + 1 + 2 = 5$ comparisons. Note the upper bound $(n - m + 1) m = 3 \cdot 2 = 6$ ; we did 5, saving one thanks to the early break at $s = 1$ .

Recap of the matrix

Recall Which example hit which cell?

Ex1 ::: A (middle) + B (start) Ex2 ::: C (right edge, $s = n - m$ ) Ex3 ::: D (no match) Ex4 ::: E (overlapping matches) Ex5 ::: F (single-char pattern, $m = 1$ ) Ex6 ::: G ( $m = n$ ) and H (empty pattern $m = 0$ ) Ex7 ::: I (worst case $Θ (nm)$ ) Ex8 ::: J (best/expected $\approx O (n)$ ) Ex9 ::: K (real-world DNA search) Ex10 ::: L (exact comparison count, exam twist)

For text of length n and all-same-char pattern of length m inside all-same-char text, how many overlapping matches?

n - m + 1

Where does an empty pattern (m=0) match in a text of length n?

At all

n + 1

positions

0

through

n

In the worst case with pattern "AA...B", how many comparisons per shift?

The full

m

— the break fires only on the last character.

Why does pattern "XY" against "ABCDEF" cost only ~n comparisons?

The first pattern char never appears, so every shift breaks after 1 comparison (best/expected case).

When m=n, how many candidate shifts are there?

Exactly one (

s = 0

Connections

Parent: the algorithm these examples exercise
KMP Algorithm — turns Ex7's $Θ (nm)$ into $O (n + m)$ by reusing matched info.
Boyer-Moore Algorithm — skips shifts like Ex8's failures even faster.
Rabin-Karp Algorithm — compares each window in $O (1)$ expected via hashing.
Big-O Notation — the language for the cost counts above.
Sliding Window Technique — the "slide the ruler" model behind every shift.
Substring Search Problem — the umbrella problem all cases belong to.