Foundations — Naive pattern matching — O(nm)

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

Is page mein zero prior knowledge assume ki gayi hai. Parent note padhne se pehle, usmein use hone wala har letter yahan ground up se build kiya gaya hai, us order mein jo har idea ko pehle waale idea ke upar rest karne deta hai.

1. Ek string numbered boxes ki ek row hoti hai

Yahan sab kuch ek string se shuru hota hai: characters ki ek ordered row. "Ordered" ka matlab hai ki position matter karti hai — "ABA" aur "AAB" same nahi hain.

Ek string ko boxes ki ek strip ki tarah picture karo, ek character per box, aur — yeh crucial habit hai — box number neeche likho, 0 se shuru karke.

• Figure dekho: sabse left waale box mein jo character hai uska index 0 hai, 1 nahi. Yeh "count-from-zero" rule code mein universal hai aur parent note har jagah isi par rely karta hai.
• Length-$L$ string ke last box ka index $==L-1==$ hota hai. Agar $L=10$ hai, toh last valid index 9 hai, kabhi bhi 10 nahi.

2. Hamare kaam ki do strings: $T$ aur $P$

Poori problem mein exactly do strings involved hain.

Dono ko ek length symbol dete hain taaki "kitna lamba" words mein kabhi na kehna pade:

Do alag letters kyun, ek ki jagah? Kyunki algorithm ki speed dono par independently depend karti hai — ek lamba text ek tiny pattern ke saath bahut alag behave karta hai ek aisi situation se jahan text aur pattern ka size similar ho. $n$ aur $m$ ko alag rakhna hi baad mein honest label $O(nm)$ likhne deta hai dono mein se ek ko hide karne ki jagah.

3. Indexing: square-bracket notation

Ek specific box ke baare mein baat karne ke liye, hume use name karne ka tarika chahiye.

• $T[0]$ = pehla character. $T[n-1]$ = aakhri character.
• Bracket ek sawaal hai jo tum string se poochte ho: "position $i$ par kaun sa letter hai?"

Hume consecutive boxes ki ek run ko bhi name karna hoga, kyunki ek match text ka ek poora stretch hota hai, na ki sirf ek letter:

Toh $T[2\dots 4]$ ek 3-character chunk hai (boxes 2, 3, 4). Gino: $4-2+1=3$. Yeh "+1" baar baar aata hai — yeh Section 1 ka wahi "count-from-zero" fingerprint hai.

4. Shift $s$ — jahan hum ruler rakhte hain

Ab asli star. Imagine karo ki pattern-ruler ko text ke saath slide kar rahe ho. Abhi woh kahan baitha hai woh ek single number hai.

• Figure mein ruler (pattern $P$) shift $s$ par rakha gaya hai. Uska box $j$ text box $s+j$ ke saath line up karta hai. Yeh ek relationship — ==pattern box $j$ ↔ text box $s+j$== — poore algorithm ka dil hai.
• Ek shift valid tab kehlata hai jab har pattern letter neeche waale text letter se match kare: $T[s\dots s+m-1]=P[0\dots m-1]$ Ise zor se padho: "$T$ ka $m$-lamba slice jo $s$ se shuru hota hai, poore pattern ke barabar hai."

5. Shifts $n-m$ par kyun rukте hain

Agar ruler ko bahut zyada right slide karein, uski tail text ke end se bahar latakti hai. Woh kab hota hai?

Pattern ka last box $s+m-1$ par land karta hai. Uske liye abhi bhi ek real text box hona zaroori hai, hume chahiye ki woh last text index $n-1$ se zyada na ho: $s+m-1\le n-1⟹s\le n-m$

• Figure mein green ruler last legal shift $s=n-m$ par baitha hai: uski tail exactly last text box ko touch karti hai.
• $s=n-m+1$ par red ruler overhang karta hai — box $m-1$ ko text box $n$ chahiye hoga, jo exist nahi karta.

Yahi wajah hai ki parent note kehta hai exactly $n-m+1$ candidates hain.

6. Counting tool: $O(\cdot )$ — Big-O

Parent ka headline "$O(nm)$" hai. Is symbol ka matlab kya hai?

Yeh tool hume exact steps count karne ki jagah kyun chahiye? Kyunki exact step count machine, language, chosen letters par depend karta hai — messy, unstable numbers. Big-O us noise ko uda deta hai aur sirf growth ka shape rakhta hai, jo actually decide karta hai "fast" versus "slow" jab inputs scale hote hain. Poori treatment ke liye Big-O Notation dekho.

• Yahan $nm$ kahan se aata hai? Outer slide $n-m+1\approx n$ baar chalti hai; har slide mein up to $m$ letter-comparisons hoti hain. Multiply karo: lagbhag $n\times m$ comparisons. Woh product hi $O(nm)$ hai.

7. Do loops aur "==" test

Parent ka pseudocode do loops aur ek equality check use karta hai. Inhe picture se build karo.

Prerequisite map

Equipment checklist

Apne aap ko test karo — har answer sirf tab reveal karo jab tum use zor se bol chuke ho.

Connections

• Parent: woh algorithm jin foundations ko feed karti hain yeh
• Substring Search Problem — woh problem jise yeh saari notation describe karti hai.
• Big-O Notation — jahan se $O(nm)$ symbol aata hai.
• Sliding Window Technique — "$s$ slide karo" picture ko generalize karta hai.
• KMP Algorithm — woh upgrade jo matched info reuse karta hai.
• Boyer-Moore Algorithm — letter rules use karke shifts skip karta hai.
• Rabin-Karp Algorithm — hashing se windows compare karta hai.