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

3.8.2 · Coding › String Algorithms

KAUNSI problem solve kar rahe hain?

KYA: Pattern $P$ (length $m$ ) ke saare occurrences text $T$ (length $n$ ) mein dhundho.

KYUN naive slow hai: Naive matching har shift par $P$ ko compare karti hai. Adversarial input jaise $T = aaaa...a$ , $P = aaa...ab$ par yeh $O (nm)$ kaam karta hai, baar baar same text characters ko re-scan karte hue.

KAISE KMP jeetta hai: Text pointer $i$ sirf aage hi move karta hai. Jab pattern position $j$ par mismatch hoti hai, $j = 0$ reset karne ki jagah, hum $j = π [j - 1]$ set karte hain — pattern ko uske longest reusable prefix par jump karte hue. Har text char amortized $O (1)$ baar "examine" hota hai → $O (n + m)$ .

Failure function $π$ (poora trick)

Worked example: `ababaca` ke liye $π$ banao

i	char	S[0..i]	longest proper prefix=suffix	π[i]
0	a	a	(none)	0
1	b	ab	(none)	0
2	a	aba	`a`	1
3	b	abab	`ab`	2
4	a	ababa	`aba`	3
5	c	ababac	(none)	0
6	a	ababaca	`a`	1

Kyun π[4]=3? ababa: prefix aba = suffix aba. Usse lamba (abab) suffix nahi hai. Toh 3.

Kyun π[5]=0? ababac c par khatam hota hai; ababac ka koi prefix c par khatam nahi hota, sivaaye poore string ke (jo proper nahi hai). Toh 0.

$π$ -computation algorithm ko scratch se DERIVE karna

Hum $π$ incrementally build karte hain. Maano humein $π [0.. i - 1]$ pata hai aur $π [i]$ chahiye. $j = π [i - 1]$ = previous position ke liye best prefix-suffix ki length.

Case 1 — extend kar sakte hain. Agar $S [i] = S [j]$ , toh prefix S[0..j-1] jo suffix tha, dono ends par ek char se badh sakta hai. Toh $π [i] = j + 1$ .

Yeh step kyun? Length $j$ ka ek border (prefix=suffix) S[0..i-1] ke liye, plus ek matching char, S[0..i] ke liye length $j + 1$ ka border deta hai.

Case 2 — mismatch, fall back karo. Agar $S [i] \neq = S [j]$ aur $j > 0$ , toh next-best candidate border length $π [j - 1]$ hai. Hum $j \leftarrow π [j - 1]$ set karte hain aur retry karte hain.

Kyun $π [j - 1]$ ? $j$ se chhota sabse lamba border jo current prefix ka bhi border ho, woh usi border ka sabse lamba border hai — jo hai $π [j - 1]$ . Yeh recursion nested borders ki chain mein neeche jaati hai.

Case 3 — bottom aa gaya. Agar $j = 0$ aur phir bhi mismatch, $π [i] = 0$ .

pi[0] = 0
for i = 1 .. m-1:
    j = pi[i-1]
    while j > 0 and S[i] != S[j]:
        j = pi[j-1]          # fall back along border chain
    if S[i] == S[j]:
        j += 1
    pi[i] = j

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

Matching loop DERIVE karna

Wohi machine text par chalao. $i$ index kare $T$ ko, $j$ index kare $P$ ko.

j = 0
for i = 0 .. n-1:
    while j > 0 and T[i] != P[j]:
        j = pi[j-1]           # mismatch → slide pattern, keep i
    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]           # continue searching for overlapping matches

Kyun mismatch par hum i ko back nahi lete? Kyunki prefix P[0..π[j-1]-1] guaranteed equal hai pehle se scan kiye gaye text ke. Dobara padhna ek jaani-maani equality ko re-confirm karna hoga. Isliye $i$ sirf aage badh'ta hai.

WHY yeh O(n+m) hai — amortized proof

Yahi key insight hai jo KMP ko naive se alag karti hai: fallback ki amortized cost is baat se bounded hai ki $j$ kabhi kitna badha.

Full match example: $P =$ `abab`, $T =$ `ababaababab`

Pehle abab ke liye $π$ : [0,0,1,2].

i (text)	T[i]	j before	action	j after
0	a	0	match	1
1	b	1	match	2
2	a	2	match	3
3	b	3	match → j=4=m, report 0, j=π[3]=2	2
4	a	2	match	3
5	a	3	mismatch (P[3]=b≠a) j=π[2]=1; P[1]=b≠a j=π[0]=0; P[0]=a==a	1
6	b	1	match	2
7	a	2	match	3
8	b	3	match → j=4, report 6, j=2	2
9	a	2	match	3
10	b	3	match → j=4, report 7, j=2	2

Kyun report 0 phir 6 phir 7? Overlapping occurrences abab indices 0, 6, 7 par. i=5 par j=3 se 1 par fallback ne matched a ko reuse kiya, restart karne ki jagah.

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho tum ek word ko letter by letter match kar rahe ho aur 5th letter par galti ho gayi. Ek bewakoof robot poori tarah peeche jaata aur poora word phir se shuru karta. Ek smart robot yaad rakhta hai: "jo last kuch letters maine abhi likhe hain woh mere word ke shuru jaisi hain!" Toh woh restart nahi karta — woh pretend karta hai ki usne pehle se shuru likh liya aur continue karta hai. "Failure function" sirf ek cheat-sheet hai jo robot ko batati hai, har jagah ke liye, ki galti hone par kitne letters woh rakh sakta hai. Kyunki yeh kabhi book ko dobara nahi padhta, yeh bahut fast hai.

Active Recall

What does the failure function π[i] store?

S[0..i] ke longest proper prefix ki length jo S[0..i] ka suffix bhi ho.

Why must the prefix in π be proper (strictly shorter)?

Warna π[i]=i+1 hamesha hoga aur fallback j=π[j-1] kabhi decrease nahi karega, infinite loop / koi progress nahi.

On a mismatch at pattern index j, what do we set j to?

j = π[j-1] (pehle se matched prefix ka longest border), text pointer fixed rakhte hue.

After a full match (j==m), why set j=π[m-1] instead of 0?

Overlapping occurrences detect karne ke liye, bina text dobara padhe.

Why is KMP matching O(n+m)?

j total ≤ n baar badhta hai (ek baar per text char) aur har while-step j ko ≥1 ghataata hai; kyunki j≥0, total decreases ≤ total increases, toh inner loop O(n) total run karta hai.

Build π for "ababaca".

[0,0,1,2,3,0,1]

What is the recurrence when S[i]==S[π[i-1]]?

π[i] = π[i-1] + 1 (previous border ko ek matching char se extend karo).

Why does the text pointer i never move backward in KMP?

Kyunki prefix P[0..π[j-1]-1] guaranteed already equal hai abhi-abhi scan kiye gaye text ke, toh use dobara padhna unnecessary hai.

Connections

Z-algorithm — alternative linear string matching Z-array ke zariye
Rabin-Karp — hashing-based matching, expected $O (n + m)$
Aho-Corasick — KMP failure links ko kaafi patterns tak generalize karta hai (a trie of fail links)
Suffix Automaton & Suffix Array — repeated queries ke liye heavier structures
Amortized Analysis — $O (n + m)$ bound ke liye use hone wala potential argument
Borders and Periods of Strings — $π [m - 1]$ $P$ ka smallest period deta hai