3.8.2 · D2 · HinglishString Algorithms
Visual walkthrough — KMP algorithm — failure function, O(n+m) — full derivation
3.8.2 · D2· Coding › String Algorithms › KMP algorithm — failure function, O(n+m) — full derivation
Step 1 — String, prefix, aur suffix kaisi dikhti hai
KYA HAI. Ek string sirf letters ki ek row hai. Hum boxes ko se number karte hain.
Toh ababa mein, box mein a hai, box mein b hai, aur aise aage. Hum likhte hain
matlab "start se lekar box tak ke saare boxes, including box ".
- A prefix ek chunk hai jo left end se liya jaata hai:
a,ab,aba, ... - A suffix ek chunk hai jo right end se liya jaata hai:
a,ba,aba, ... - Proper matlab hai "poori string nahi" — strictly shorter.
YEH DO WORDS KYUN. KMP ki poori trick ek aisi chunk ke baare mein hai jo prefix bhi hai aur suffix bhi ek saath. Humein "left se chunk" aur "right se chunk" ke naam chahiye taakin hum ek aisi chunk ke baare mein baat kar sakein jo dono ho.
PICTURE. Green bracket left se slide karta hai (prefix); orange bracket right se slide karta hai (suffix). Jahan ek green chunk aur orange chunk ki same letters hoon, humne kuch special dhundh liya hai.
Step 2 — kya measure karta hai: ab tak ka sabse lamba border
KYA HAI. Har box ke liye, sirf piece dekho (string jo box par cut off ho). Pucho: iska sabse lamba border kitna lamba hai? Woh number mein store karo.
\underbrace{\text{proper prefix}}_{\text{from the left}}\ \text{that equals a } \underbrace{\text{suffix}}_{\text{from the right}}\ \text{of } S[0..i].$$ Us line ke pieces padhte hue: answer ek **length** hai (boxes ki count), prefix **left se** measure hota hai, aur yeh string ko **right se** padh kar bhi match karna chahiye. **LENGTH STORE KYUN KAREIN, CHUNK KHUD NAHI.** Length ek single small number hai. Agar $\pi[4]=3$ hai toh hum turant jaante hain "pehle 3 letters last 3 letters ke barabar hain" bina letters store kiye. Bas yehi KMP ko ever chahiye hota hai. **PICTURE.** `ababaca` ke liye hum har cut-off piece draw karte hain aur uska sabse lamba border mark karte hain. Jahan koi left-chunk right-chunk se match nahi karta, border length $0$ hai. ![[deepdives/dd-coding-3.8.02-d2-s02.png]] > [!formula] `ababaca` ke liye array > $$\pi = [\,0,\ 0,\ 1,\ 2,\ 3,\ 0,\ 1\,]$$ > $\pi[0]=0$ hamesha: ek single box ka koi *proper* prefix hi nahi hota. --- ## Step 3 — Mismatch ke baad border exactly wahi hai jo tum reuse karte ho **KYA HAI.** Ab pattern $P$ ko text $T$ se match karte hue socho. Maan lo pehle $j$ letters match ho gaye, phir $P[j]$ ne text se **disagree** kiya. Woh $j$ matched letters dono jagah hain: woh text ka ek chunk bhi hain *aur* pattern ka prefix $P[0..j-1]$ bhi. **BORDER KYUN JEETTA HAI.** Humare saamne wala text us matched chunk ke kisi suffix par khatam hota hai. Agar $P$ ka koi **prefix** us suffix ke barabar ho — yaani ek border — toh woh prefix text ke saath *pehle se sahi se line up* hai. Hum pattern ko slide karte hain taaki uska border wahan baitha ho jahan matched suffix tha, aur hum woh letters **dobara check nahi karte**. Choosing the **longest** border slides the **least** distance, so we can never jump over a real match. **PICTURE.** Upar: red mismatch tak match kiya hua pattern. Beech mein: matched part ke andar green border orange suffix bhi hai. Neeche: green ko slide karo jahan orange tha — text pointer $i$ (blue) kabhi nahi hila. ![[deepdives/dd-coding-3.8.02-d2-s03.png]] > [!intuition] Ek sentence jo yaad rakhna hai > "Jo letters maine pehle se match kar liye hain unmein mere pattern ke beginning ki ek chhoti copy hai — > toh main *wahan* se restart karta hun, zero se nahi." --- ## Step 4 — $\pi$ build karna: "extend" case ($S[i]=S[j]$) **KYA HAI.** Hum $\pi$ left to right build karte hain. Maan lo hum pehle se jaante hain $j=\pi[i-1]$ — pichle cut-off piece ke liye best border length. Ab hum ek naaya box, $S[i]$, add karte hain. Agar naya letter $S[i]$, $S[j]$ ke barabar hai (woh letter jo purane border ke just baad baitha hai), toh border **dono** ends par ek se badh jaata hai: $$\pi[i] \;=\; \underbrace{j}_{\text{old border length }=\ \pi[i-1]}\; +\; 1.$$ **YEH KYUN KAAM KARTA HAI.** $j$ length ka purana border matlab hai "$S[0..i-1]$ ke pehle $j$ letters = last $j$ letters". Prefix ke *baad* wala letter $S[j]$ hai; suffix ke *baad* wala letter brand-new $S[i]$ hai. Agar woh equal hain, toh prefix aur suffix dono us ek shared letter se extend ho jaate hain → length $j+1$ ka border. **PICTURE.** Green prefix aur orange suffix dono ek aur matching letter (blue box) nigal lete hain. Border counter exactly $1$ se upar tick karta hai. ![[deepdives/dd-coding-3.8.02-d2-s04.png]] --- ## Step 5 — $\pi$ build karna: "fall back" case ($S[i]\ne S[j]$) **KYA HAI.** Agar naya letter **match nahi karta** ($S[i]\ne S[j]$) aur $j>0$ hai, toh hum extend nahi kar sakte. Lekin shayad ek **shorter** border abhi bhi kaam kare. Agla candidate length hai $\pi[j-1]$ — *current border ka* sabse lamba border: $$j \;\leftarrow\; \underbrace{\pi[j-1]}_{\text{longest border of the length-}j\text{ border}}.$$ Phir hum $S[i]=S[j]$ ko chhote $j$ ke saath dobara test karte hain, aur tab tak repeat karte hain jab tak match ho ya $j$ $0$ tak na pahunch jaaye. **$\pi[j-1]$ KYUN AUR KOI NAHI.** $j$ se chhota koi bhi border jo poore prefix mein fit ho, woh khud length-$j$ border ka bhi border hona chahiye (ek "border of a border"). Aisa sabse lamba nested border exactly $\pi[j-1]$ par stored hai. Toh fall-back chain $j \to \pi[j-1] \to \pi[\pi[j-1]-1] \to \dots$ saare candidates ko decreasing order mein walk karti hai, koi bhi miss kiye bina. **PICTURE.** Nested-border chain: bade green border ke andar ek chhota green border hai; jab bada fail ho jaata hai toh hum chhote par girte hain. Har red cross ek failed extend hai; har arrow ek $j\leftarrow\pi[j-1]$ hop hai. ![[deepdives/dd-coding-3.8.02-d2-s05.png]] > [!mistake] $\pi[j-1]$ ki jagah $\pi[j]$ use karna > $j$ *matched letters* count karta hai, isliye last matched index $j-1$ hai. Matched > prefix ka border $\pi[j-1]$ par hai. $\pi[j]$ use karna ek aisa box read karta hai > jise tumne kabhi match hi nahi kiya. --- ## Step 6 — Degenerate cases: bottom out karna aur empty border **KYA HAI.** Do edge situations ko handle karna zaroori hai warna machine toot jaayegi: 1. **$j$ $0$ tak pahunch jaaye aur phir bhi mismatch ho.** Koi border bacha nahi; naya letter fresh start karta hai. $\pi[i]=0$ set karo. 2. **$\pi[0]=0$ hamesha.** Ek single-letter piece ka koi *proper* prefix hi nahi hota, isliye uska sabse lamba border length $0$ hai. Yahi woh seed hai jis par poori recursion khadi hai. **YEH KYUN MATTER KARTE HAIN.** Case 1 ke bina fall-back loop $\pi[-1]$ read karne ki koshish karta aur crash ho jaata. Proper-prefix rule ke bina, "sabse lamba border" hamesha poori string hoti ($\pi[i]=i+1$), fall-back kabhi $j$ ko shrink nahi karta, aur matching forever loop karta. **PICTURE.** Left: fall-back chain $j=0$ tak poori tarah run karti hai, koi green bachta nahi, toh $\pi[i]=0$. Right: forbidden "whole-string border" — kyun yeh ban hai. ![[deepdives/dd-coding-3.8.02-d2-s06.png]] > [!mistake] Poori string ko border count karne dena > Poori string khud ki ek suffix hai aur yeh sabse lambi hai — tempting lagta hai. Lekin yeh > **proper nahi** hai. Isko allow karne se $\pi[i]=i+1$ milta hai, fall-back kabhi decrease nahi karta, aur > algorithm kabhi terminate nahi hota. Borders *strictly shorter* hone chahiye. --- ## Step 7 — Matching, aur kyun text pointer kabhi reverse nahi karta **KYA HAI.** Wahi machine text $T$ par run karo. Pointer $i$, $T$ ko scan karta hai; pointer $j$ matched pattern letters count karta hai. Mismatch par hum $j\leftarrow\pi[j-1]$ karte hain **aur $i$ ko fixed rakhte hain**. Full match par ($j=m$) hum position $i-m+1$ report karte hain, phir **overlapping** matches catch karne ke liye $j\leftarrow\pi[m-1]$ set karte hain. **$i$ SIRF FORWARD KYUN JAATA HAI.** $j\leftarrow\pi[j-1]$ ke baad, prefix $P[0..\,\pi[j-1]-1]$ *guaranteed* hai ki scanned text ke barabar hai. Use dobara padhna sirf ek jaani-maani equality re-confirm karta — pure waste. Isliye $i$ kabhi peeche nahi jaata. **PICTURE.** `P=abab` ko `T=ababaababab` par chalane ka timeline. Blue text pointer $i$ poori row mein strictly rightward move karta hai; orange pattern pointer $j$ upar jaata hai (matches) aur girta hai (fall-backs). Reports indices $0$, $6$, $7$ par milti hain. ![[deepdives/dd-coding-3.8.02-d2-s07.png]] > [!example] $i=5$ par trace padhna > Pehle: $j=3$. Text letter hai `a`, lekin $P[3]=$`b` → mismatch. Fall back > $j=\pi[2]=1$; ab $P[1]=$`b`$\ne$`a` → fall back $j=\pi[0]=0$; ab $P[0]=$`a`$=$`a` → > match, $j=1$. Humne single matched `a` **reuse** kiya cold restart karne ki jagah. --- ## Step 8 — Yeh $O(n+m)$ kyun hai: $j$ ko rise aur fall karte hue dekho **KYA HAI.** Sirf $j$ track karke total work count karo. - Text ke $n$ steps mein se har ek $j$ ko **at most $1$** se badhata hai (single `j += 1`). - Har fall-back `while` step $j$ ko **at least $1$** se ghataata hai (kyunki $\pi[j-1]<j$). - $j$ $0$ se start hota hai aur kabhi negative nahi ja sakta. $$\underbrace{(\text{total rises})}_{\le\, n} \;\ge\; \underbrace{(\text{total falls})}_{=\ \#\text{ while-steps}} \quad\Longrightarrow\quad \#\text{ while-steps} \le n.$$ **YEH POORA SPEED ARGUMENT KYUN HAI.** Inner loop har text character ke liye *$O(n)$* nahi hai — **poore run** mein yeh at most $n$ baar fire karta hai, kyunki tum $j$ se zyaada subtract nahi kar sakte jitna tumne add kiya. Yeh "har rise ke liye ek baar pay karo" idea [[Amortized Analysis]] hai. Wahi count $\pi$ build karne ke liye $O(m)$ deta hai, toh total $O(n+m)$ hai. **PICTURE.** $j$ ka time ke saath sawtooth. Total upward area (green) $=$ total downward area (red). Kyunki $i$ at most $n$ up-ticks contribute karta hai, down-ticks bhi $n$ se cap hain. ![[deepdives/dd-coding-3.8.02-d2-s08.png]] --- ## Ek-picture summary Yeh single figure sab kuch compress karta hai: $\pi$ build karo extending ya falling back se (Steps 4–6), phir un numbers ko use karo pattern ko text mismatch par slide karne ke liye bina $i$ move kiye (Steps 3, 7), sab kuch rise-and-fall bound se pay kiya hua (Step 8). ![[deepdives/dd-coding-3.8.02-d2-s09.png]] > [!recall]- Poore walkthrough ki Feynman retelling > String matlab boxes mein letters. **Border** ek aisa chunk hai jo ek piece ka start bhi hai aur > end bhi — jaise `ababa` ke andar `aba`. Har cut-off length ke liye hum uske sabse lambe border ka > size likh lete hain; woh list hai $\pi$. > > $\pi$ build karne ke liye: ab tak ka best border rakho. Ek letter add karo. Agar prefix ke baad wala letter > naye letter se match karta hai, border ek se badh jaata hai. Agar nahi, toh us border ke > *andar* wale border par jao (woh hai $\pi[j-1]$) aur dobara try karo, zero tak jaate hue. > > Search karne ke liye: wahi machine text par run karo. Jab koi letter disagree kare, toh > restart mat karo — pattern ko $\pi[j-1]$ par jump down karo aur text finger exactly wahan rakho jahan > hai, kyunki chhota border pehle se sahi line up hai. Full match? Report karo > aur $\pi[m-1]$ par jump karo taaki overlapping copies miss na ho. > > Yeh fast kyun hai? Counter $j$ at most ek baar per text letter upar jaata hai aur sirf utna hi neeche > aa sakta hai jitna upar gaya. Toh saara "jumping down" milake us se zyaada cost nahi karta jitne text > letters hain. Linear time, no backtracking. Done. --- ## Active Recall > [!recall] Khud ko test karo > - `ababa` mein, border ka naam batao aur uski length do. > - $\pi$ build karte waqt, border length exactly $1$ se kab badhti hai? > - Jab woh nahi badh sakti, $j$ kis value par girta hai, aur kyun *wahi* ek? > - Matching ke dauran kaun sa pointer peeche jaane se forbidden hai? > - Ek sentence mein woh up/down argument batao jo $O(n+m)$ prove karta hai. `ababa` ka border aur uski length? ::: `aba`, length $3$ (pehle teen letters last teen letters ke barabar, aur poori string se shorter). $\pi$ build karte waqt border exactly kab $1$ se badhta hai? ::: Jab $S[i]=S[\pi[i-1]]$ — naya letter purane border ke just past wale letter ke barabar ho, prefix aur suffix dono saath extend ho. Build/match mismatch par hum $j=\pi[j-1]$ set karte hain; woh slot kyun? ::: Yeh current border ka sabse lamba border hai (border of a border) — next-longest candidate, toh $j$ shrink karte waqt koi miss nahi hota. Matching ke dauran kaun sa pointer kabhi peeche nahi jaata, aur kyun? ::: Text pointer $i$; fallen-back prefix pehle se scanned text se match karta hai, isliye use dobara padhna wasted work hai. $O(n+m)$ ka one-sentence proof? ::: $j$ at most ek baar per text step badhta hai ($\le n$ total) aur har fall-back use $\ge 1$ se ghataata hai, toh total fall-backs $\le n$ — overall linear.