Naive pattern matching — O(nm) — Coding notes

WHAT is the problem?

$T$ = "ABABCABABA", $P$ = "ABA". We want every place "ABA" sits inside $T$ .
A shift $s$ is valid if all $m$ characters line up.

WHY does the naive method work at all?

HOW does it run? (derive the pseudocode from scratch)

We build it step by step from the definition.

We must consider every shift $s$ from $0$ to $n-m$ . → outer loop.
For a fixed $s$ , "is this shift valid?" means: compare $P[0]$ with $T[s]$ , $P[1]$ with $T[s+1]$ , … → inner loop over $j = 0 \ldots m-1$ .
The moment any character mismatches, this shift is dead — break early (optimization), no point checking the rest.
If the inner loop finishes without breaking, all $m$ chars matched → record $s$ .

NAIVE-MATCH(T, P):
    n = len(T);  m = len(P)
    for s = 0 to n - m:           # candidate start positions
        j = 0
        while j < m and T[s+j] == P[j]:
            j = j + 1
        if j == m:                # inner loop ran to completion
            report match at s

Worked example Trace: T = "ABABCABABA", P = "ABA"

$n=10,\ m=3$ , so shifts $s=0\ldots7$ .

$s$	compare	result
0	A=A, B=B, A=A	MATCH ✅
1	B≠A	fail at $j=0$
2	A=A, B=B, C≠A	fail at $j=2$
3	B≠A	fail
4	C≠A	fail
5	A=A, B=B, A=A	MATCH ✅
6	B≠A	fail
7	A=A, B=B, A=A	MATCH ✅

Matches at $s = 0, 5, 7$ . Why this step? At each $s$ we restart $j=0$ and walk the pattern; one mismatch kills the shift. This is the whole algorithm in action.

WHY is it O(nm)? (derive the bound)

Common mistake Steel-manning the common errors

1. "Loop $s$ from 0 to $n$ ." Why it feels right: the text has $n$ positions, so it seems natural to scan all of them. Why it's wrong: for $s > n-m$ the pattern overruns the end → out-of-bounds access. Fix: stop at $s = n-m$ (inclusive), i.e. for s in range(n - m + 1).

2. "Naive is always slow / always O(nm)." Why it feels right: the worst case is $O(nm)$ and that's the headline figure. Why it's wrong: on random / English text mismatches usually happen on the first 1–2 characters, so the inner loop almost never reaches $m$ . Average behavior is close to $O(n)$ . Fix: distinguish worst case from expected case.

3. Forgetting the early break. Why it feels right: "I'll just compare all $m$ chars and check a flag." It still gives correct answers. Why it's wrong: it throws away the cheap speedup — without break you always do $m$ comparisons. Fix: break/while-condition on first mismatch.

4. Reusing partial info across shifts. Why it feels right: "I already compared some chars, surely I can skip ahead." That's actually the correct intuition — but naive matching deliberately does not do it; it forgets everything and restarts $j=0$ . Using that information is exactly what upgrades you to KMP.

Recall Feynman: explain to a 12-year-old

Imagine you have a long sentence and a short word written on a transparent ruler. You lay the ruler at the very start of the sentence and check letter by letter: does the first letter match? second? If all letters of the little word match the letters underneath, you found it! If at any point a letter is wrong, you stop, slide the ruler one step to the right, and try again from the beginning of the word. You keep sliding until the ruler reaches the end of the sentence. That sliding-and-checking is the whole trick. It's simple but can be slow because every time you slide, you start checking from scratch.

Active Recall

How many candidate starting positions does naive matching check for text length n and pattern length m?

n - m + 1

(positions

0

through

n-m

); beyond that the pattern overruns the text.

What is the worst-case time complexity of naive pattern matching?

O(nm)

— more precisely

\Theta((n-m+1)m)

Give a worst-case input for naive matching.

Text all same char like "AAAA…A" with pattern "AAA…AB" — every shift matches

m-1

chars then fails on the last.

Why can naive matching behave like O(n) in practice?

On typical/random text, mismatches occur in the first 1–2 characters, so the inner loop rarely runs near

m

times.

What single idea distinguishes naive matching from KMP?

Naive forgets all comparison info and restarts

j=0

each shift; KMP reuses already-matched info to skip redundant comparisons.

What is the role of the early break in the inner loop?

Stop comparing as soon as one character mismatches — saves work without changing the result.

What defines a "valid shift" s?

A shift where

T[s..s+m-1] = P[0..m-1]

, i.e. all

m

characters line up.

Connections

KMP Algorithm — removes redundant rechecks using a prefix function → $O(n+m)$ .
Boyer-Moore Algorithm — skips ahead using bad-character/good-suffix rules.
Rabin-Karp Algorithm — hashes windows to compare in $O(1)$ expected.
Big-O Notation — basis for the $O(nm)$ analysis.
Sliding Window Technique — the "slide the pattern" view generalizes here.
Substring Search Problem — the parent problem this solves.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Naive pattern matching ka idea bilkul simple hai: tumhare paas ek bada text $T$ hai (length $n$ ) aur ek chhota pattern $P$ hai (length $m$ ), aur tumhe dhoondhna hai ki $P$ text ke andar kahan-kahan aata hai. Tareeka? Pattern ko text ke upar slide karo — pehle position 0 par rakho, fir 1, fir 2... har position par letter-by-letter check karo ki match ho raha hai ya nahi. Agar saare $m$ characters match ho gaye to wahan ek match mil gaya; agar beech mein koi ek bhi mismatch hua to turant ruk jao (early break) aur agle position par slide kar do.

Kitni positions check karni padti hain? Sirf $0$ se $n-m$ tak, yaani $n-m+1$ positions — kyunki uske aage pattern text se bahar nikal jaayega. Har position par worst case mein $m$ comparisons lagte hain, isliye total time $O(nm)$ ho jaata hai. Yeh worst case tab aata hai jab text mein bahut repetition ho, jaise $T=$ "AAAAA" aur $P=$ "AAB" — har baar last character par jaake fail hota hai, full kaam karna padta hai.

Practical baat: real English text ya random data par yeh actually kaafi fast chalta hai, kyunki zyadatar jagah pehle ya doosre character par hi mismatch ho jaata hai, to inner loop chhota reh jaata hai — almost $O(n)$ behave karta hai. Lekin guarantee nahi de sakte, isliye worst case ke liye KMP, Boyer-Moore ya Rabin-Karp jaise smart algorithms aaye, jo pehle se match kiya hua information reuse karke redundant comparisons skip karte hain. Naive ki sabse badi "kamzori" yahi hai ki har slide par wo sab kuch bhool kar $j=0$ se phir shuru karta hai.

Naive pattern matching — O(nm)

WHAT is the problem?

WHY does the naive method work at all?

HOW does it run? (derive the pseudocode from scratch)

WHY is it O(nm)? (derive the bound)

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections