Visual walkthrough — Naive pattern matching — O(nm)

3.8.1 · D2 · Coding › String Algorithms › Naive pattern matching — O(nm)

Yeh Naive pattern matching — O(nm) ka companion note hai. Pehle woh padhna pseudocode ke liye; yeh padhna isse dekhne ke liye.

Step 1 — Kaagaz ki do strips

KYA. Hum do cheezein se shuru karte hain aur kuch nahi. Ek lambi strip — text — aur ek chhoti strip — pattern. Har chhota box exactly ek character hold karta hai.

KYUN. Kisi bhi formula se pehle, humein raw ingredients ke liye naam chahiye. Poora problem yeh hai: chhoti strip lambi strip ke upar exactly kahan baith ti hai? Agar hum dono strips ko picture nahi kar sakte, toh koi bhi baad ka symbol kuch matlab nahi rakhega.

PICTURE. Figure dekho. Upar ki row text hai; maine har box ke neeche ek chhota number likha hai — woh number us box ki position hai, $0$ se ginti karte hue. Hum $0$ se count karte hain ($1$ se nahi) kyunki code mein array indexing aise hi kaam karti hai, aur yeh poora page asal mein code ki ek picture hai.

Step 2 — "Mil gaya" ka matlab kya hai?

KYA. Hum chhoti strip ko slide karte hain taaki uska left edge text ke box number $s$ ke upar baith jaye. Woh number $s$ shift kehlata hai. Hum kehte hain shift kaam karta hai (yaani valid hai) jab pattern ka har box seedha uske neeche wale box se match karta hai.

KYUN. "Word dhundho" vague hai. Isse kuch aisa banana ke liye jo ek machine check kar sake, humein ise ek number $s$ ke baare mein ek precise haan/na ke sawaal mein badalna hoga. Figure $s=5$ pe parked pattern dikhata hai: pattern box $0$ text box $5$ ke upar, pattern box $1$ text box $6$ ke upar, pattern box $2$ text box $7$ ke upar.

PICTURE. Teen violet arrows follow karo. Har ek pattern box ko us text box se pair karta hai jise usse equal hona chahiye.

Step 3 — Strip kitna slide ho sakti hai?

KYA. Hum poochhte hain: left edge $s$ ke liye legal resting places kya hain? Strip bilkul shuru se slide ho sakti hai ($s=0$) us aakhri jagah tak jahan uska right box ek real text box pe land karta hai.

KYUN. Agar hum zyada slide kar dein, toh pattern ka right end text ke edge se aage "empty air" mein chala jaata hai — compare karne ke liye koi box nahi hoga, aur code array se aage padhne pe crash ho jaayega. Toh ek last legal shift hota hai, aur legal shifts ko count karna poori time analysis ka beej hai.

PICTURE. Figure teen positions dikhata hai: sabse left ($s=0$), ek middle wala, aur sabse right legal wala. Notice karo ki pattern ka right box us last position mein exactly last text box pe land karta hai. Ek aur step right aur woh gir jaata hai (faded/red draw kiya hua).

Step 4 — EK shift check karna: spell it out

KYA. Strip ko ek shift $s$ pe freeze karo. Ab hum counter $j$ use karke pattern ke andar ek chhota left-to-right scan chalate hain: box $0$ compare karo, phir box $1$, phir box $2$... Jaise hi ek pair disagree kare, ruk jaao.

KYUN. Ek single failed letter hi prove kar deta hai ki yeh shift dead hai — yeh poora match nahi ho sakta, toh baki check karna wasted breath hai. Jaldi rokna early break hai. Isse answer kabhi nahi badalta (dead shift dead rehti hai); sirf kaam bachta hai.

PICTURE. Figure $s=2$ pe hamare example ka scan dikhata hai. Pehle do boxes pe green checks (A=A, B=B), phir $j=2$ pe red cross jahan $C\ne A$. Scan ruk jaata hai — daayein faded box pe nazar bhi nahi jaati.

Step 5 — Lucky case: pehle hi box pe mismatch

KYA. Kabhi kabhi pehla hi comparison ($j=0$) fail ho jaata hai. Tab poora inner scan sirf ek comparison lamba hota hai.

KYUN. Humein yeh case cover karna hai kyunki yahi naive matching ko real life mein fast banata hai. Ordinary English ya random text pe, zyaataar shifts box $0$ ya box $1$ pe mar jaate hain — pattern ka pehla letter rarely random text letter se match karta hai.

PICTURE. Figure $s=1$ dikhata hai (B under A → instant red cross at $j=0$) aur $s=4$ (C under A → instant cross). In shifts mein se har ek ko sirf ek comparison lagta hai, $m$ nahi. "Kaam kiya" wala green bar ek sliver hai.

Step 6 — Killer case: mismatch hamesha LAST box pe

KYA. Ab hum jaan-boojhkar sabse bura input banate hain. Text sab ek letter ka ho, $T=$ "AAAAAAAAA", aur pattern ho $P=$ "AAAB". Har shift pe pehle $m-1$ boxes match karte hain (saare A's), aur sirf last box fail karta hai (B vs A).

KYUN. Yahan early break bekaar hai — yeh kabhi jaldi trigger nahi hota, kyunki failure bilkul last box pe chhupi hoti hai. Har single shift marne se pehle poore $m$ comparisons pay karta hai. Yahi case $nm$ headline number force karta hai, aur exactly yahi redundancy hai jo KMP Algorithm aur Boyer-Moore Algorithm mitate karne ke liye banaye gaye the.

PICTURE. Figure kai shifts stacked dikhata hai. Har row mein pehle teen boxes green hain (A=A) aur chautha red cross hai (B≠A). Green work-bars saari full width hain — maximum kaam, har baar.

Step 7 — Strips ke neeche ka area = running time

KYA. Har shift ko horizontal bar ki tarah stack karo, uski length = us shift ne kitne comparisons kiye. Total kaam saari bars ki total length hai — literally picture ka area.

KYUN. Yeh "kitna slow?" ko "shaded region kitna bada hai?" mein convert karta hai — kuch jo tum dekh sako. Sabse uncha possible tower mein $n-m+1$ bars hain (ek per shift), har ek zyaada se zyaada $m$ lamba. Toh shaded area kabhi bhi height $(n-m+1)$ aur width $m$ ke rectangle se zyaada nahi ho sakta.

PICTURE. Left panel: real text — zyaataar bars chhote slivers hain, shaded area chhota hai ($O(n)$ jaisa behave karta hai). Right panel: killer text — har bar full width $m$ hai, shaded area poora $(n-m+1)\times m$ rectangle fill karta hai.

Ek-picture summary

Upar sab kuch compressed: candidate shifts (Step 3) → inner scan with early break (Step 4) → lucky-vs-killer (Steps 5–6) → area = time (Step 7).

Active Recall

Connections

• Naive pattern matching — O(nm) — parent note with pseudocode aur full trace.
• KMP Algorithm — matched info yaad rakhta hai $j=0$ pe restart karne ki jagah → $O(n+m)$.
• Boyer-Moore Algorithm — worst case ko aage skip karke khatam karta hai.
• Rabin-Karp Algorithm — poori windows ko hash se $O(1)$ expected mein compare karta hai.
• Big-O Notation — area-to-time argument ki language.
• Sliding Window Technique — "strip slide karo" mental model generalized.
• Substring Search Problem — parent problem jo yeh solve karta hai.

Concept Map