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

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

Do machines ka reminder jo aap baar baar use karte rahenge:

"Border" ek short word hai uss string ke liye jo ek proper prefix bhi ho aur proper suffix bhi ho. Picture dekho: do shaded blocks equal hain, isliye string ababa ka ek border aba hai jiska length $3$ hai.

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

Level 1 — Recognition

L1.1 — Definition se ek value padho

Problem. $S = aabaa$ ke liye, $π [4]$ haath se compute karo (last position).

Recall Solution

$S [0..4] = aabaa$ . Hume longest border chahiye.

Length 4 candidate aaba vs suffix abaa — nahi.
Length 3 candidate aab vs suffix baa — nahi.
Length 2 candidate aa vs suffix aa — haan.

Toh $π [4] = 2$ . (Length 1 a=a bhi kaam karta hai lekin 2 bada hai, toh hum 2 rakhte hain.)

L1.2 — Poora table bharo

Problem. $S = aabaaab$ ke liye poora $π$ array banao.

Recall Solution

Position by position chalo, hamesha woh longest prefix lo jo $S [0.. i]$ ka suffix bhi ho:

i	S[0..i]	border	π[i]
0	a	—	0
1	aa	`a`	1
2	aab	—	0
3	aaba	`a`	1
4	aabaa	`aa`	2
5	aabaaa	`aa`	2
6	aabaaab	`aab`	3

Toh $π = [0, 1, 0, 1, 2, 2, 3]$ . $i = 5$ dhyan se dekho: aabaaa — aaa? aisa koi prefix nahi; border aa hi rehta hai.

Level 2 — Application

L2.1 — Build machine chalao, apni aankhein nahi

Problem. Code use karo (intuition nahi) $S = abacabab$ ke liye $π$ compute karne ke liye. Har step par $j$ dikhao.

Recall Solution

Build loop yaad karo: j=pi[i-1]; while j>0 and S[i]!=S[j]: j=pi[j-1]; if S[i]==S[j]: j+=1; pi[i]=j.

i	S[i]	start j	while-jumps	S[i]==S[j]?	π[i]
1	b	0	—	b≠a → nahi	0
2	a	0	—	a==a → +1	1
3	c	1	S[3]=c≠S[1]=b → j=π[0]=0	c≠a → nahi	0
4	a	0	—	a==a → +1	1
5	b	1	S[5]=b==S[1]=b	haan → +1	2
6	a	2	S[6]=a==S[2]=a	haan → +1	3
7	b	3	S[7]=b==S[3]=c? nahi → j=π[2]=1; S[7]=b==S[1]=b	haan → +1	2

$π = [0, 0, 1, 0, 1, 2, 3, 2]$ .

L2.2 — Match machine chalao

Problem. $P = aba$ ke saath (toh $π = [0, 0, 1]$ ), $T = ababa$ mein saare occurrences dhundho. Start indices (0-based) list karo.

Recall Solution

Match loop $i$ ko aage badhata rehta hai, $j$ matched pattern chars count karta hai.

i	T[i]	j before	action	j after
0	a	0	match	1
1	b	1	match	2
2	a	2	match → j=3=m, report 0, j=π[2]=1	1
3	b	1	match	2
4	a	2	match → j=3=m, report 2, j=π[2]=1	1

Occurrences indices 0 aur 2 par start hote hain (overlapping — beech ka a share hota hai).

Level 3 — Analysis

L3.1 — Proper clause optional kyun nahi hai

Problem. Maano koi $π^{'} [i]$ define karta hai poori string ko allow karte hue longest prefix=suffix ke roop mein. Match loop par trace karo jab pehla mismatch aata hai aur precisely failure explain karo.

Recall Solution

"Improved" definition ke saath, har position ko $π^{'} [i] = i + 1$ milta hai (poori substring apna khud ka longest prefix-and-suffix hai). Ab pattern index $j$ par mismatch aata hai. Fallback hai $j \leftarrow π^{'} [j - 1] = j$ . Matlab: $j$ change nahi hota. while j>0 and T[i]!=P[j] condition abhi bhi true hai (same $j$ , same mismatch), toh hum $j$ frozen ke saath loop karte hain — ek infinite loop. Proper clause exactly yahi guarantee karta hai ki $π [j - 1] < j$ ho, toh har jump strictly $j$ ko shrink karta hai aur loop terminate karna padta hai.

L3.2 — Total fallback work count karna

Problem. $T$ (length $n$ ) mein $P$ (length $m$ ) match karne ke liye, ek tight upper bound do ki match loop ka inner while body total kitni baar run ho sakta hai, aur justify karo ki $j$ kaise change hota hai.

Recall Solution

Single variable $j$ ko poori run mein watch karo.

$j$ sirf badhta hai j+=1 mein, ek baar per outer iteration, aur $n$ outer iterations hain → total increase $\leq n$ .
Har while body $j \leftarrow π [j - 1]$ karta hai jahan $π [j - 1] < j$ hai, toh har body $j$ ko kam se kam 1 se decrease karta hai.
$j$ $0$ se shuru hota hai aur kabhi negative nahi hota, toh total decrease $\leq$ total increase $\leq n$ .

Isliye while body poori match mein zyada se zyada $n$ baar run hoti hai, per character nahi. Yahi $O (n + m)$ bound ka amortized heart hai. "Sawtooth" dekho: $j$ ek step at a time chadhta hai aur utna hi gir sakta hai jitna chadha tha.

Level 4 — Synthesis

L4.1 — Ek string ka smallest period

Problem. Ek string $S$ (length $m$ ) ka period sabse chhota $p \geq 1$ hai jo ki $S [k] = S [k + p]$ satisfy kare sabhi valid $k$ ke liye. Prove karo ki smallest period $m - π [m - 1]$ hai, phir isse $S = ababab$ par apply karo.

Recall Solution

Border ⇔ period link. Agar $S$ ka length $b$ ka border hai, toh length $b$ ka prefix length $b$ ke suffix ke barabar hai. Unhe overlay karne par $S [k] = S [k + (m - b)]$ milta hai har jagah jo overlap karti hai — toh $m - b$ ek period hai. Ulta, ek period $p$ se length $m - p$ ka border milta hai. Toh longest border ⇔ smallest period, aur $p_{m i n} = m - (longest border) = m - π [m - 1] .$ Apply karo. $S = ababab$ , $m = 6$ . Iska $π$ hai $[0, 0, 1, 2, 3, 4]$ , toh $π [5] = 4$ . Phir $p_{m i n} = 6 - 4 = 2$ . Sach mein ababab block ab ko repeat karta hai jiska length $2$ hai. ✓

L4.2 — Kya $S$ kisi chhote block ki repetition hai?

Problem. " $S$ kisi block ki $k \geq 2$ copies hai" ke liye ek one-line test do ( $π$ use karke), aur isse abcabcabc aur abcab par test karo.

Recall Solution

$S$ kisi block ki $k \geq 2$ full copies hai agar aur sirf agar iska smallest period $p = m - π [m - 1]$ $m$ ko divide kare aur $p < m$ ho. Tab $k = m / p$ .

abcabcabc: $m = 9$ , $π [8] = 6$ , toh $p = 9 - 6 = 3$ . $3 ∣ 9$ aur $3 < 9$ → haan, abc ki $k = 9/3 = 3$ copies. ✓
abcab: $m = 5$ , $π [4] = 2$ , toh $p = 5 - 2 = 3$ . $3 ∤ 5$ → clean repetition nahi. ✓

Level 5 — Mastery

L5.1 — KMP se longest palindromic prefix

Problem. $S$ diya gaya hai, hume iska longest prefix chahiye jo palindrome ho. Dikhao ki isse EK prefix-function computation se kaise nikala jaaye, aur isse $S = abacab$ par run karo. (Hint: reverse aur ek separator.)

Recall Solution

$R$ = $S$ ka reverse, aur banao $C = S + # + R$ , jahan # ek aisa character hai jo $S$ mein kaheen nahi aata. $C$ par $π$ compute karo. Kyun kaam karta hai: $π [last index of C]$ = $S$ ka longest prefix jo $R$ ka suffix bhi ho. $R$ ka suffix (ulta karke) $S$ ka prefix backwards padha hai; isse $S$ ke prefix se match karna us prefix ko forwards aur backwards same padhne par majboor karta hai — ek palindromic prefix. # border ko beech se cross karne se rokta hai, toh value $∣ S ∣$ se zyada nahi ho sakti. Run karo. $S = abacab$ , $R = bacaba$ , $C = abacab#bacaba$ (length 13). $C$ par $π$ compute karte hain, last value $π [12] = 3$ hai, prefix aba match karta hai. Toh abacab ka longest palindromic prefix length 3 ka hai (aba). ✓

L5.2 — Distinct border lengths count karo

Problem. $S$ ke saare border lengths ka set (saare proper prefixes jo suffix bhi hain) exactly ${π [m - 1], π [π [m - 1] - 1], \dots}$ hai, $0$ tak. $S = aabaaab$ use karke (L1.2 se, $π = [0, 1, 0, 1, 2, 2, 3]$ ), poori string ke saare border lengths list karo.

Recall Solution

Last index se shuru karo: $π [6] = 3$ . Phir $π [len - 1]$ ke through chain chase karo:

length $3$ → next $π [3 - 1] = π [2] = 0$ .
length $0$ → ruko.

Toh border lengths hain ${3, 0}$ ; trivial empty border ko ignore karke, aabaaab ka sirf ek non-trivial border hai jiska length 3 hai (block aab). $π$ -chain ko tail se chase karna har border ko enumerate karta hai, longest pehle, borders ki sankhya ke proportional time mein.

Recall Aage kahan jaana hai

Wahi border/period ideas Borders and Periods of Strings ko power karte hain.
Z-values par build ek alag linear-matcher: Z-algorithm.
Hashing-based matching (alag trade-offs): Rabin-Karp.
Ek saath kai patterns: Aho-Corasick; heavy string machinery: Suffix Automaton, Suffix Array.
L3.2 mein amortized argument Amortized Analysis ka ek case study hai.

Active Recall

Longest border of aabaaab?

length 3 (block aab)

Smallest period of ababab?

2, since

6 - π [5] = 6 - 4 = 2

Is abcab a clean repetition of a block?

Nahi — iska period 3 uski length 5 ko divide nahi karta

On a full match, set j to?

π [m - 1]

, overlaps rakhne ke liye