Foundations — KMP algorithm — failure function, O(n+m) — full derivation

3.8.2 · D1 · Coding › String Algorithms › KMP algorithm — failure function, O(n+m) — full derivation

Yeh the KMP topic ka foundations page hai. Hum har woh symbol build karte hain jo parent note use karta hai, "string kya hoti hai" se shuru karke "what does $\pi [i]$ mean" tak pahunchte hain. Agar ek samajhdar 12-saal-ka baccha line one padhna shuru kare, toh use koi bhi aisa symbol nahi milna chahiye jise define nahi kiya gaya ho.

1. Ek string, aur usme point karne ka tarika

Yeh baat karne ke liye ki kaun sa moti hai, hum positions ko number karte hain. Programmers 0 se count karna shuru karte hain, 1 se nahi.

Neeche diya figure string ababaca ko saat rounded boxes mein dikhata hai. Har box ek character rakhta hai; har box ke neeche teal number uska index hai. Dekho pehle box par $0$ label hai (orange arrow) aur aakhri box par $6$ label hai (plum arrow).

Toh string ababaca ke liye:

• $S[0]=\text{a}$, $S[1]=\text{b}$, $S[2]=\text{a}$, … $S[6]=\text{a}$.

2. Length $m$, length $n$

Agar $P=\text{abab}$ hai toh $m=4$. Valid indices $P[0]$ se lekar $P[m-1]=P[3]$ tak hain — aakhri index hamesha $m-1$ hota hai, $m$ nahi. Yeh "off-by-one" sabse common bug ka source hai, isliye isse achhi tarah pakad lo. (Yahi reason hai kyun hum indexing 0 se shuru karte hain: "$i$ text index par match khatam hoti hai, isliye yeh $i-m+1$ par shuru hui thi" jaisi formula sirf 0-based indices ke saath kaam karti hai.)

3. Empty string

Strings ko kaatne se pehle, hume ek special string chahiye jo miss karna aasan hai.

4. Substring aur slice $S[a..b]$

ababaca ke liye, $S[\mathrm{0..2}]=\text{aba}$ aur $S[\mathrm{2..4}]=\text{aba}$ dobara (same letters, alag location).

Figure mein, teen orange-tinted boxes slice $S[\mathrm{0..2}]$ mark karte hain; teal double-headed arrow exactly un teen cells ko span karta hai yeh dikhane ke liye ki slice positions 0, 1, 2 inclusive ko cover karti hai — teen characters, word aba.

Parent note bahut baar $S[\mathrm{0..}i]$ likhta hai — woh hamesha bilkul shuru se position $i$ tak ka slice hota hai, yaani pehle $i+1$ characters. Yeh ek growing window hai jo chhoti shuru hoti hai aur jaise-jaise $i$ badhta hai, right ki taraf aur aage jaati hai.

5. Prefix aur suffix — ek slice ke do sire

Yeh do words KMP ka dil hain. Sab kuch inhi par depend karta hai.

Dekho dono lists $\epsilon$ se shuru hoti hain (kuch nahi pakdo) aur puri string par khatam hoti hain (sab kuch pakdo). Empty string hamesha appear hoti hai — yahan se length-0 borders aati hain.

Figure mein ababa ki do copies stack ki gayi hain. Upar wali copy par orange highlight ek prefix mark karta hai (aba, left se liya gaya); neeche wali copy par teal highlight ek suffix mark karta hai (aba, right se liya gaya). Same letters, opposite ends.

6. Proper vs. whole

ababa ke liye: ababa khud ek prefix aur suffix hai, lekin ek proper nahi. Proper prefixes hain $\epsilon ,\text{a},\text{ab},\text{aba},\text{abab}$ — pura word chhod kar sab kuch.

7. Border — ek prefix jo suffix bhi hai

ababa ke liye:

• $\epsilon$ (empty string) hamesha ek border hai — length 0. ✓
• a ek border hai (prefix a, suffix a). ✓
• aba ek border hai (prefix aba, suffix aba). ✓
• abab ek prefix hai lekin suffix nahi hai → border nahi.

Kyunki $\epsilon$ hamesha ek border hai, kisi bhi string ke liye border lengths ki list kabhi empty nahi hoti — usme kam se kam $0$ hota hai.

Figure mein ababa ki ek copy dikhti hai jisme prefix aba upar orange mein bracket kiya gaya hai aur suffix aba neeche teal mein bracket kiya gaya hai. Woh alag positions par hain lekin same letters rakhte hain — yahi coincidence aba ko border banati hai, aur uski length (3) neeche plum color mein answer hai.

ababa ka sabse lamba border aba hai, length 3. Woh number 3 dimag mein rakho — yeh exactly wahi value hai jo failure function report karega.

8. Failure function $\pi$ — sab kuch jodna

Ab har ingredient define ho chuka hai, isliye parent ki definition clearly padhti hai.

• $\pi$ numbers ki ek array hai, ek number har position ke liye.
• $\pi [0]=0$ hamesha: slice $S[\mathrm{0..0}]$ ek single character hai. Uska ek hi proper prefix hai — empty string $\epsilon$, jiski length $0$ hai — isliye sabse lambe border ki length $0$ hai.

9. Big-O — $O(n+m)$ ka actually kya claim hai

10. Match pointer $j$ (ek aage ki jhalak)

Ek aur symbol neeche diye map mein appear karta hai, isliye use abhi meet karo.

11. Pieces topic ko kaise feed karte hain

Diagram top to bottom padho. Har arrow ka matlab hai "neeche wale box ko samajhne ke liye upar wale box ki zarurat hai". String / index se shuru karo: yeh tumhe length $m,n$ aur growing slice $S[\mathrm{0..}i]$ ke baare mein baat karne deta hai. Ek slice ke do sire hote hain — ek prefix aur ek suffix; sirf proper wale rakhna aur poochna ki prefix kaahan suffix ke barabar hai, ek border define karta hai; har position par sabse lambe border ki length $\pi [i]$ hai. Aakhir mein, match pointer $j$ aur $\pi$ milkar KMP ka fallback $j\leftarrow \pi [j-1]$ dete hain, aur puri machine right mein diye $O(n+m)$ budget ke andar chalti hai.

Equipment checklist

Cover the right side and answer; reveal to check.