KMP algorithm — failure function, O(n+m) — full derivation: Question bank

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

Shuru karne se pehle, ye plain-language anchors apne dimaag mein rakh lo:

Recall Vocabulary refresher (agar koi word shaky lage toh open karo)

Prefix of a string = ek chunk jo front se liya gaya ho (e.g. ab of abcd).
Suffix = ek chunk jo back se liya gaya ho (e.g. cd of abcd).
Proper prefix/suffix = ek jo puri string se strictly shorter ho (matlab puri string apna khud ka proper prefix nahi hoti).
Border = ek string jo dono proper prefix aur proper suffix ho. Failure function $π [i]$ length of the longest border of $S [0.. i]$ store karta hai.
Text pointer $i$ text $T$ mein chalti hai; pattern pointer $j$ count karta hai ki abhi kitne pattern characters match ho rahe hain.

Ye ideas Borders and Periods of Strings se connect hote hain — length $b$ ka border $L$ length ki string mein matlab hai string ki period $L - b$ hai.

Ye page self-contained hai. Neeche ke do code snippets wahi machinery hain jo tumhe chahiye; har "Spot the error" aur "Why" item in exact lines ko refer karta hai, isliye inhe nazaron ke saamne raho.

Formula

$π$ -build machine (teen cases yahan hain)

pi[0] = 0
for i = 1 .. m-1:
    j = pi[i-1]
    while j > 0 and S[i] != S[j]:   # Case 2: mismatch → fall back
        j = pi[j-1]
    if S[i] == S[j]:                # Case 1: characters agree → extend
        j += 1
    pi[i] = j                       # Case 3: j hit 0, no border

Case 1 (extend): $S [i] = S [j]$ , toh length $j$ ka border grow hokar $j + 1$ ho jaata hai.
Case 2 (fall back): $S [i] \neq = S [j]$ aur $j > 0$ , toh next-shorter border par shrink karo $j \leftarrow π [j - 1]$ aur retry karo.
Case 3 (bottom out): $j = 0$ aur phir bhi koi match nahi, toh $π [i] = 0$ .

Formula Match machine (wahi automaton, text par run karo)

j = 0
for i = 0 .. n-1:
    while j > 0 and T[i] != P[j]:   # inner while: mismatch fallback
        j = pi[j-1]
    if T[i] == P[j]:
        j += 1
    if j == m:                      # full match ending at i
        report match at i-m+1
        j = pi[j-1]                 # keep overlap, don't reset to 0

Why questions

Mechanism se jawab do, restatement se nahi.

Border reuse karne se pattern minimum safe distance slide kyun hoti hai?

Longest border sabse bada overlap hai jo pehle se text ke saath match hone ke liye jaana jaata hai, toh

m - π [m - 1]

se slide karna (sabse chota shift) kisi real occurrence ko jump over nahi kar sakta — chota border aur aage slide karega aur match skip karne ka risk hoga.

Fallback chain

j \to π [j - 1] \to \dots

kyun finite aur hamesha terminating hai?

Har step strictly chota border length deta hai (

π [j - 1] < j

), toh sequence non-negative integers mein strictly decreasing hai aur finite steps mein

0

tak pahunchni chahiye.

Amortized cost argument mein hum

i

ki jagah variable

j

kyun track karte hain?

j

"potential" hai: ye per outer step zyada se zyada

1

rise karta hai aur har expensive while iteration apna cost

j

drop karke khud chukati hai. Total decrease ko total increase se bound karna hidden work cap kar deta hai — ye ek textbook Amortized Analysis hai.

Naive matcher aaaa...ab vs aaaa par

O (n + m)

kyun achieve nahi kar sakta?

Naive har mismatch par saare matched characters throw away kar deta hai aur unhe next shift par re-scan karta hai, toh wo same as ka run

O (m)

baar per position re-read karta hai — bilkul wahi re-reading jo KMP ka forward-only

i

forbid karta hai.

Matching ke liye

π

hi kaafi information kyun hai, pattern ka structure kisi aur tarike se store kiye bina?

π

har prefix ki border chain fully encode karta hai, aur match loop ko sirf "given maine

j

chars match kiye aur abhi fail hua, next-best matched length kya hai?" — jo exactly ek

π

lookup hai.

Z-algorithm same matching problem kaise solve karta hai lekin alag array meaning ke saath?

Z har position ke liye longest substring ki length store karta hai jo wahan se shuru hoke prefix se match karti hai — ek "forward" view;

π

har position par end hone wala longest border store karta hai — ek "backward" view. Dono

O (n + m)

matching dete hain, same self-similarity ko alag tarike se encode karke.

π [m - 1]

(last value) exactly pattern ke longest border ki length kyun hai?

S [0.. m - 1]

puri pattern hai, toh iska longest proper prefix jo suffix bhi hai — final index par

π

ki definition — by definition pattern ka longest border hai.

Edge cases

Boundary inputs jahan galat code silently break ho jaata hai.

Length

1

ke pattern ke liye

π

kya hai, maan lo x?

Sirf [0]. Ek character ka koi proper prefix nahi hai, toh array ek single zero hai — aur matching phir bhi kaam karta hai, x ke barabar har text position par hit report karta hai.

Kya hota hai agar pattern text se lamba ho (

m > n

j

kabhi

m

nahi pahunch sakta kyunki outer loop sirf

n < m

baar chalta hai aur

j

har step mein zyada se zyada

1

rise karta hai. Sahi taur par, koi match report nahi hota.

Text aaaaaaa mein pattern aaaa ke liye kitne matches hain aur overlap kyun hai?

Chaar matches (indices 0,1,2,3 par). Har full match ke baad hum

j = π [3] = 3

set karte hain, teen matched as rakhte hue, toh agla match ek position baad shuru hota hai — overlapping runs capture ho jaate hain, skip nahi hote.

Agar pattern mein saare distinct characters hain, e.g. abcd, toh

π

kaisa dikhta hai?

Sab zeros: [0,0,0,0]. Jab har character unique ho toh koi prefix kisi suffix ke barabar nahi ho sakta, toh kisi bhi mismatch par

j

seedha

0

par reset ho jaata hai — KMP gracefully naive-like behavior mein degenerate ho jaata hai lekin phir bhi

O (n + m)

rehta hai.

Empty string ka

π

kya hai, aur kya code uske liye well-defined hai?

Empty string ke koi indices nahi hain, toh

π

ek empty array hai; build loop (i = 1 .. m-1) simply kabhi nahi chalta. Koi special-casing nahi chahiye — loop bounds usse handle kar lete hain.

abcabcab jaise periodic pattern ke liye, last

π

value tumhe kya batata hai?

π [7] = 5

(border abcab), aur period hai

m - π [m - 1] = 8 - 5 = 3

— repeating block abc ke saath match karta hua. Ye border↔period link Borders and Periods of Strings ka bridge hai.

Agar do alag patterns ka same

π

array ho, toh kya KMP unpar identically behave karta hai?

Nahi.

π

fallback structure control karta hai, lekin actual character comparisons

T [i]

P [j]

real letters par depend karti hain — same skip-logic, alag match outcomes.

Mirror-image "forward" formulation ke liye, Z-algorithm se compare karo; many-patterns-at-once ke liye, ye machine Aho-Corasick tak generalize hoti hai. Heavier index-structure alternatives Suffix Automaton, Suffix Array ke neeche hain.

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

True or false — justify

Spot the error

Why questions

Edge cases