Naive pattern matching — O(nm): Visual walkthrough

Everything below is built from two strings. Let us name them once and never assume anything else.

We use $T = "ABABCABABA"$ (so $n = 10$ ) and $P = "ABA"$ (so $m = 3$ ) throughout.

Step 1 — Draw the two strings as a ruler over a tape

WHAT. Picture the text $T$ as a fixed tape, one box per character. Picture the pattern $P$ as a short transparent ruler you can slide left-to-right over that tape.

WHY. Before any comparing, we must see the one operation the whole algorithm is made of: placing the ruler at some position $s$ . If we cannot picture placement, we cannot picture the search.

PICTURE. The tape is fixed; the ruler starts at the far left, $s = 0$ .

Step 2 — Where is the ruler allowed to sit?

WHAT. Find the last legal position for the left edge $s$ .

WHY. If we slide the ruler too far right, its right edge $s + m - 1$ points past the end of the tape — there is no character there to compare. So there is a hard wall. Finding it tells us exactly how many placements exist, which will directly control the running time later.

PICTURE. The last legal placement is when the ruler's right edge touches the tape's last box.

Step 3 — At one placement, spell it out box by box

WHAT. Fix $s = 0$ . Walk a pointer $j$ from $0$ upward, comparing $P [j]$ against the text box underneath it, which is $T [s + j]$ .

WHY. Placement alone proves nothing — we must check whether the letters actually agree. The pointer $j$ is our reading finger moving along the ruler. We compare left to right because we want to stop at the first disagreement (next step).

PICTURE. Green boxes = matched so far; the finger $j$ advances only while letters agree.

Step 4 — A full match: the finger reaches the end

WHAT. If the finger $j$ walks all the way to $j = m$ without ever finding a mismatch, every letter agreed. Record $s$ as a valid shift.

WHY. $j = m$ is the signal "I compared all $m$ letters and none failed." That is exactly the definition of the pattern occurring at $s$ . Reaching the end is the only way to earn a match.

PICTURE. All three ruler boxes are green; $s = 0$ is stamped as a hit.

Step 5 — A mismatch: stop early and slide

WHAT. Now move to $s = 1$ . Compare $P [0] = A$ against $T [1] = B$ . They differ immediately. We stop — no point checking $P [1], P [2]$ — and slide the ruler one box right to $s = 2$ .

WHY. Once a single pair disagrees, this placement can never become a full match. Continuing to compare would be wasted work. Stopping at the first mismatch is the early break; it never changes the answer, only saves effort. And we slide by exactly one box because naive matching throws away everything it just learned and restarts fresh (the thing KMP Algorithm later fixes).

PICTURE. Red box marks the first mismatch; a curved arrow shows the ruler jumping one step right.

Step 6 — The whole slide across the tape

WHAT. Repeat placement + spelling for every $s = 0 \dots 7$ and collect all valid shifts.

WHY. The naive method is correct by exhaustion: it tries every legal placement, so it cannot miss a real occurrence and cannot invent a fake one. Seeing all eight placements stacked makes the "try everything" nature visible.

PICTURE. Eight stacked rows, one per shift; green rows are the hits.

Step 7 — The worst case: why the cost is $O (nm)$

WHAT. Swap to the adversarial input $T = "AAAAAAAAA"$ ( $n = 9$ ), $P = "AAAB"$ ( $m = 4$ ). Now at every placement the finger walks $A = A = A$ (three matches) and only fails on the last letter $B$ .

WHY. The early break was our savior — but here it never triggers early. Each of the $n - m + 1$ placements pays the full $m$ comparisons before dying. Stacking those columns of near-full work is where the product $nm$ literally appears as area on the page.

PICTURE. Each row is almost entirely green with a single red box at the far right — a wall of wasted work.

The one-picture summary

One diagram, the whole derivation: the ruler ( $P$ , width $m$ ) slides over the tape ( $T$ , length $n$ ); it may sit in $n - m + 1$ spots; at each spot a finger spells left-to-right and stops on the first red; the total shaded area — placements times comparisons — is the $O (nm)$ cost.

Recall Feynman: retell the walkthrough with no symbols

You have a long sentence written on a paper strip and a short word written on a see-through ruler. You put the ruler at the very left. Then you read left to right: does the ruler's first letter match the paper letter under it? Second? If all of them match, you've found the word — mark that spot. The moment one letter is wrong, you stop reading (why keep going, it's already ruined?) and slide the ruler one notch to the right, starting your reading over from the ruler's first letter. You keep sliding until the ruler's right end would fall off the paper — that's your stopping wall. Most of the time on real sentences the very first letter is wrong, so you barely read anything and it's fast. But if the paper is "AAAAAAAA" and the word is "AAAB", every single time you read almost the whole word before the final B ruins it — so you do the maximum reading at every stop. Add up "number of stops" times "letters read per stop" and that rectangle of work is the famous $O (nm)$ .

Connections

Naive pattern matching — O(nm) — the parent this page illustrates.
KMP Algorithm — reuses the info Step 5 throws away.
Boyer-Moore Algorithm — slides by more than one box using skip rules.
Rabin-Karp Algorithm — replaces the per-box spelling with one hash compare.
Sliding Window Technique — the "slide the ruler" motion, generalized.
Substring Search Problem — the problem all of this solves.
Big-O Notation — why the shaded area is written $O (nm)$ .