Naive pattern matching — O(nm) — Hinglish notes

3.8.1 · Coding › String Algorithms

Problem KYA hai?

$T$ = "ABABCABABA", $P$ = "ABA". Hume har woh jagah chahiye jahan "ABA" $T$ ke andar baithta hai.
Ek shift $s$ valid hai agar saare $m$ characters line up ho jayein.

Naive method kaam KYUN karta hai?

Yeh RUN kaise karta hai? (pseudocode scratch se derive karo)

Hum ise definition se step by step banate hain.

Hume har shift $s$ , $0$ se $n - m$ tak consider karna hai. → outer loop.
Ek fixed $s$ ke liye, "kya yeh shift valid hai?" ka matlab hai: $P [0]$ ko $T [s]$ se compare karo, $P [1]$ ko $T [s + 1]$ se, … → inner loop $j = 0 \dots m - 1$ par.
Jaise hi koi bhi character mismatch ho, yeh shift khatam — break early (optimization), baaki check karna bekar hai.
Agar inner loop bina break ke khatam ho jaye, toh saare $m$ chars match ho gaye → $s$ record karo.

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$ , toh shifts $s = 0 \dots 7$ .

$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 $s = 0, 5, 7$ par milte hain. Yeh step kyun? Har $s$ par hum $j = 0$ se restart karte hain aur pattern ko walk karte hain; ek mismatch shift ko khatam kar deta hai. Yeh poora algorithm action mein hai.

Yeh O(nm) KYUN hai? (bound derive karo)

Common mistake Common errors ko steel-man karna

1. "Loop $s$ ko 0 se $n$ tak chalao." Kyun sahi lagta hai: text mein $n$ positions hain, toh sabko scan karna natural lagta hai. Kyun galat hai: $s > n - m$ ke liye pattern end se bahar chala jata hai → out-of-bounds access. Fix: $s = n - m$ par ruko (inclusive), matlab for s in range(n - m + 1).

2. "Naive hamesha slow hai / hamesha O(nm) hai." Kyun sahi lagta hai: worst case $O (nm)$ hai aur yahi headline figure hai. Kyun galat hai: random / English text par mismatches usually pehle 1–2 characters mein hi hote hain, toh inner loop kabhi $m$ ke paas nahi pahunchta. Average behavior $O (n)$ ke kareeb hota hai. Fix: worst case aur expected case mein fark karo.

3. Early break bhool jaana. Kyun sahi lagta hai: "Main bas saare $m$ chars compare kar lunga aur ek flag check karunga." Sahi answers deta hai phir bhi. Kyun galat hai: yeh sasta speedup kho deta hai — break ke bina tum hamesha $m$ comparisons karte ho. Fix: pehle mismatch par break/while-condition lagao.

4. Shifts ke paas partial info reuse karna. Kyun sahi lagta hai: "Maine kuch chars pehle compare kar liye, surely aage skip kar sakta hoon." Yeh actually sahi intuition hai — lekin naive matching deliberately yeh nahi karta; woh sab bhool kar $j = 0$ se restart karta hai. Us information ka use karna hi tumhe KMP ki taraf upgrade karta hai.

Recall Feynman: 12-saal ke bacche ko samjhao

Socho tumhare paas ek lamba sentence hai aur ek chhota word ek transparent ruler par likha hai. Tum ruler ko sentence ki bilkul shuruat mein rakhte ho aur letter by letter check karte ho: pehla letter match karta hai? doosra? Agar chhote word ke saare letters neeche wale letters se match karein, toh tumne dhundh liya! Agar koi bhi letter galat ho, tum ruk jaate ho, ruler ko ek step daayein slide karte ho, aur word ki shuruat se dobara try karte ho. Tum tab tak slide karte rehte ho jab tak ruler sentence ke end tak na pahunch jaye. Yahi sliding-and-checking poori trick hai. Yeh simple hai lekin slow ho sakta hai kyunki har baar slide karne par tum scratch se check shuru karte ho.

Active Recall

Naive matching text length n aur pattern length m ke liye kitne candidate starting positions check karta hai?

n - m + 1

(positions

0

n - m

tak); iske baad pattern text se bahar nikal jaata hai.

Naive pattern matching ki worst-case time complexity kya hai?

O (nm)

— zyada precisely

Θ ((n - m + 1) m)

Naive matching ke liye ek worst-case input do.

Text mein sab same char jaise "AAAA…A" aur pattern "AAA…AB" — har shift

m - 1

chars match karta hai phir aakhri par fail hota hai.

Naive matching practice mein O(n) jaisa kyun behave karta hai?

Typical/random text par, mismatches pehle 1–2 characters mein hi hote hain, toh inner loop kabhi

m

ke kareeb nahi chalta.

Naive matching ko KMP se alag kaarne wala ek idea kya hai?

Naive saari comparison info bhool kar har shift par

j = 0

se restart karta hai; KMP already-matched info reuse karke redundant comparisons skip karta hai.

Inner loop mein early break ka kya role hai?

Jaise hi ek character mismatch ho, compare karna band karo — result change kiye bina kaam bachta hai.

"Valid shift" s ko kya define karta hai?

Woh shift jahan

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

, matlab saare

m

characters line up ho jayein.

Connections

KMP Algorithm — prefix function use karke redundant rechecks hatata hai → $O (n + m)$ .
Boyer-Moore Algorithm — bad-character/good-suffix rules use karke aage skip karta hai.
Rabin-Karp Algorithm — windows ko hash karta hai taaki $O (1)$ expected mein compare ho.
Big-O Notation — $O (nm)$ analysis ka aadhar.
Sliding Window Technique — "pattern slide karna" wala view yahan generalize hota hai.
Substring Search Problem — parent problem jo yeh solve karta hai.