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

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

Intuition Yeh page kis liye hai

Parent note ne machine banai. Yahaan hum use haath se chalate hain — har tarah ke input par — normal patterns, all-same strings, no-match strings, empty edge cases, overlapping hits, aur ek exam trap. Is page ke baad tumhe koi bhi KMP input aisa nahi milna chahiye jo tumne pehle na dekha ho.

Do tools jo hum baar baar use karte hain (parent mein define hue, yahan dobara bata dete hain taaki kuch assume na karna pade):

$π [i]$ = length of the ==longest proper prefix of $S [0.. i]$ that is also a suffix== of $S [0.. i]$ . "Proper" = strictly shorter than the whole chunk. Ise aise socho — do windows ek hi string ke upar slide kar rahi hain — ek left edge se chipki, ek right edge se — aur $π [i]$ batata hai ki ye kitna aage badh sakti hain jab tak unke letters agree karte rahen.
Mismatch hone par hum $j \leftarrow π [j - 1]$ jump karte hain, text pointer $i$ ko kabhi nahi chhute.

Scenario matrix

Har KMP input inhi case classes mein se kisi ek mein aata hai. Har row ek aisa tarika hai jisme machine alag behave karti hai; har class ko neeche kam se kam ek worked example mila hai.

#	Case class	Kya trigger karta hai	Kya dekhna hai
A	Generic pattern, kuch internal repetition	repeat + break ka mix	π mein bump phir reset
B	All-same string `aaaa`	har char equal	π $0, 1, 2, 3$ climb karta hai — longest chain
C	No border anywhere `abcd`	sab chars distinct	π sab zero
D	Degenerate / empty ( $m = 0$ ya $m = 1$ )	tiny input	$π [0] = 0$ , report karne ko koi match nahi
E	Overlapping matches in $T$	pattern's border ≥ 1	full-match fallback se next hit milta hai
F	No match at all in $T$	pattern absent	kuch report nahi, phir bhi $O (n)$
G	Deep fallback chain (nested borders)	lamba partial phir mismatch	ek hi $i$ par `while` kai baar chalta hai
H	Worst-case naive killer `aaa…ab` in `aaaa…`	adversarial	KMP phir bhi linear; steps gino

Intuition banana — the two-window picture

Magenta window ek prefix hai (left se chipki hui). Orange window ek suffix hai (right se chipki hui). $π [i]$ woh sabse badi length hai jis par ye dono windows identical letters rakhti hain. Jab hum "fall back" karte hain to hum magenta window ko uske apne longest self-match tak shrink karte hain — yahi woh border-of-a-border chain hai jo parent ne derive ki thi.

Case A — generic pattern `ababd`

Worked example

S = ababd ke liye $π$ banao Forecast: padhne se pehle $π$ guess karo. Kya trailing d use 0 par reset karega?

$π [0] = 0$ . Kyun: ek char a ka koi proper prefix nahi — compare karne ke liye kuch strictly chhota hai hi nahi.
$i = 1$ , ab. $j = π [0] = 0$ ; $S [1] = b$ vs $S [0] = a$ compare karo → mismatch, $j = 0$ → $π [1] = 0$ . Kyun: ab ka koi prefix uske suffix ke barabar nahi.
$i = 2$ , aba. $j = π [1] = 0$ ; $S [2] = a = S [0] = a$ → match, $j + + = 1$ → $π [2] = 1$ . Kyun: prefix a suffix a ke barabar hai; windows ek se badhi.
$i = 3$ , abab. $j = π [2] = 1$ ; $S [3] = b = S [1] = b$ → match, $j = 2$ → $π [3] = 2$ . Kyun: border ab ne pehle wale border a ko extend kiya.
$i = 4$ , ababd. $j = π [3] = 2$ ; $S [4] = d$ vs $S [2] = a$ → mismatch. $j > 0$ hai to fall back $j = π [1] = 0$ ; $S [4] = d$ vs $S [0] = a$ → mismatch, $j = 0$ → $π [4] = 0$ . Kyun: d kisi bhi prefix mein nahi aata, to koi border survive nahi karta.

Answer: $π = [0, 0, 1, 2, 0]$ .

Verify: $i = 3$ ke liye, abab: prefix ab = suffix ab ✓, aur aba suffix nahi hai, isliye 2 maximal hai. $i = 4$ ke liye, ababd: d se khatam hone wala jedha self-suffix hai woh poori string hai — jo proper nahi — isliye 0 ✓.

Cell hit: A (bump phir reset).

Case B — all-same `aaaa` (the longest chain)

Cell hit: B (monotone climb).

Case C — all-distinct `abcd` (all zeros)

Cell hit: C (zero-border baseline).

Case D — degenerate inputs

Worked example

$m = 1$ (S = x) aur empty $m = 0$ Forecast: ek letter ke pattern ke liye $π$ kya hoga? Agar pattern empty ho to kya hoga?

$m = 1$ : loop for i=1..m-1 zero times chalta hai. Sirf $π [0] = 0$ set hota hai. Kyun: ek character ka koi proper prefix nahi, compute karne ko kuch hai hi nahi.
x ko text axbx mein match karna: jab bhi $T [i] = x$ hota hai $j = 1 = m$ → report, phir $j = π [0] = 0$ . Matches indices 1 aur 3 par milte hain.
$m = 0$ (empty pattern): convention ke anusaar empty string har position $0.. n$ par match karti hai. Build loop aur match loop ke paas compare karne ko kuch nahi hai; apne code mein if m==0 se guard karo.

Answer: single-char pattern har occurrence par report karta hai; empty pattern ek boundary case hai jise tum special-case karte ho, kabhi crash nahi karna.

Verify: x in axbx → matches at ${1, 3}$ ✓ (x ki positions). Koi fallback kabhi nahi chala kyunki $π$ mein sirf slot 0 hai.

Cell hit: D (degenerate/edge).

Case E + G — overlapping matches with deep fallback: `aabaa` in `aabaabaaaabaa`

Worked example

T = aabaabaaaabaa mein saare P = aabaa dhundho Forecast: pattern aa se shuru aur khatam hota hai, isliye occurrences overlap ho sakti hain. Guess karo kitni aur kahan.

Step 0 — aabaa ke liye $π$ banao:

$π [0] = 0$ .
$i = 1$ aa: $a = a$ → $π [1] = 1$ .
$i = 2$ aab: $j = 1$ , $S [2] = b \neq = S [1] = a$ ; fall $j = π [0] = 0$ ; $b \neq = a$ → $π [2] = 0$ .
$i = 3$ aaba: $j = 0$ , $a = S [0]$ → $π [3] = 1$ .
$i = 4$ aabaa: $j = 1$ , $S [4] = a = S [1] = a$ → $π [4] = 2$ .

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

Step 1 — machine chalao. $T = aabaabaaaabaa$ (indices 0..12). $j$ track karo:

$i$	$T [i]$	$j$ in	action	$j$ out
0	a	0	match	1
1	a	1	match	2
2	b	2	match ( $P [2] = b$ )	3
3	a	3	match	4
4	a	4	match → $j = 5 = m$ report 0, $j = π [4] = 2$	2
5	b	2	match	3
6	a	3	match	4
7	a	4	match → $j = 5$ report 3, $j = 2$	2
8	a	2	$P [2] = b \neq = a$ fall $j = π [1] = 1$ ; $P [1] = a = a$ match	2
9	a	2	$P [2] = b \neq = a$ fall $j = π [1] = 1$ ; $P [1] = a = a$	2
10	b	2	$P [2] = b = b$ match	3
11	a	3	match	4
12	a	4	match → $j = 5$ report 8, $j = 2$	2

Answer: matches indices ${0, 3, 8}$ par start hote hain.

$i = 8, 9$ par fallbacks kyun? Index 3 par report karne ke baad $j = 2$ tha (reused aa). Extra as ki wajah se $b$ -comparisons fail ho gayi, isliye hum border chain $2 \to 1$ par chale — ek a rakhte hue sab throw nahi kiya. Yahi case G hai, multi-step while.

Verify: aabaa ki occurrences: index 0 (aabaab..), index 3 (aabaaab..? check: T[3..7]=aabaa ✓), index 8 (T[8..12]=aabaa ✓). 0 aur 3 yahan kuch share nahi karte, lekin fallback machinery overlapping case jaisi hi hai.

Cells hit: E (overlap-capable pattern) aur G (deep fallback chain).

Case F — pattern absent: `abc` in `ababab`

Worked example

T = ababab mein P = abc search karo Forecast: kya abc milta hai? Dekho pointer kabhi crash nahi karta.

Step 0 — abc ke liye $π$ : sab distinct → $[0, 0, 0]$ (Case C).

Step 1 — run:

$i$	$T [i]$	$j$ in	action	$j$ out
0	a	0	$a = P [0]$ match	1
1	b	1	$b = P [1]$ match	2
2	a	2	$P [2] = c \neq = a$ , $j > 0$ fall $j = π [1] = 0$ ; $P [0] = a = a$ match	1
3	b	1	match	2
4	a	2	$c \neq = a$ fall $j = 0$ ; $a = a$	1
5	b	1	match	2

$j$ kabhi $3 = m$ tak nahi pahuncha. Answer: koi match nahi; report set $\emptyset$ hai.

Verify: abc actually ababab mein nahi aata (koi c hai hi nahi) ✓. Total while iterations sirf 2 the ( $i = 2$ aur $i = 4$ par), jo confirm karta hai ki no-match input par bhi linearity rehti hai.

Cell hit: F (no match).

Case H — worst-case naive killer: `aaab` in `aaaaaaab`

Worked example

T = aaaaaaab ( $n = 8$ ) mein P = aaab search karo Forecast: naive as ke run ko baar baar rescan karta ( $O (nm)$ ). KMP ke actual steps gino.

Step 0 — aaab ke liye $π$ :

$π [0] = 0$ ; $i = 1$ aa→1; $i = 2$ aaa→2; $i = 3$ aaab: $j = 2$ , $S [3] = b \neq = S [2] = a$ fall $j = π [1] = 1$ ; $b \neq = S [1] = a$ fall $j = π [0] = 0$ ; $b \neq = S [0] = a$ → $π [3] = 0$ .

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

Step 1 — aaaaaaab par run karo (indices 0..7). Pehle chaar as $j : 0 \to 1 \to 2 \to 3$ push karte hain. $i = 3$ par $T [3] = a$ , $P [3] = b$ → mismatch, fall $j = π [2] = 2$ ; phir bhi $T [3] = a = P [2] = a$ ? Haan → $j = 3$ . To har naya a $j = 3$ tak climb karta hai phir 2 par gir ke dobara chadhta hai — har position par ek fall, poora rescan nahi.

$i$	$T [i]$	$j$ in	outcome	$j$ out
0..2	a	0→2	teen matches	3
3	a	3	$b \neq = a$ fall to 2; $a = a$	3
4	a	3	fall to 2; $a = a$	3
5	a	3	fall to 2; $a = a$	3
6	a	3	fall to 2; $a = a$	3
7	b	3	$P [3] = b = b$ match → $j = 4 = m$ report 4	$π [3] = 0$

Answer: index $8 - 4 = 4$ par single match ( $T [4..7] = aaab$ ).

Adversarial input ke bawajood linear kyun? Total while fallbacks $= 4$ (har $i = 3..6$ par ek), har baar $j$ exactly 1 se ghatta, jo pehle ke $+ 1$ increases se pay ho gaya. Yahi Amortized Analysis wala amortized/potential argument hai — total decreases $\leq$ total increases $\leq n$ .

Verify: match at index 4; aaab exactly ek baar aata hai ✓. Fallback count 4 $\leq n = 8$ ✓.

Cell hit: H (worst-case adversary, phir bhi $O (n + m)$ ).

Potential picture

Har +1 step $j$ ko ek se uthata hai; har while step use kam se kam ek se girta hai. Kyunki $j$ 0 se shuru hota hai aur har rise ek matched text char kharch karta hai (jinka total $\leq n$ hai), total drop kabhi total rise se zyada nahi ho sakta. Yahi poora $O (n + m)$ guarantee hai, ek aise staircase ki tarah visualise karo jo utna hi gir sakti hai jitni chadhti hai. Exactly border par kyun girti hai, yeh dekhne ke liye Borders and Periods of Strings dekho.

Yahan se aage kahan jaate hain

Recall KMP apne cousins se kaise relate karta hai

Z-algorithm wahi "longest match from each position" question answer karta hai, lekin rolling border ki jagah poore pattern ke prefix ke against measure karta hai.
Rabin-Karp exact border trick ki jagah hash use karta hai — average $O (n + m)$ lekin collision risk ke saath.
Aho-Corasick KMP ka failure function hai jo ek saath kai patterns ke liye trie par generalise ho jaata hai.
Suffix Automaton aur Suffix Array text ko ek baar index karte hain taaki kai pattern queries answer ho sakein.

Active Recall

Which π array does an all-same string aaaa produce?

[0, 1, 2, 3]

— the maximal climbing chain.

Which π array does an all-distinct string abcd produce?

[0, 0, 0, 0]

— no border ever forms.

In aabaa search, why did

i = 8, 9

trigger the while loop?

Extra as failed the b comparison at

j = 2

, so we fell

2 \to 1

along the border chain, reusing one a.

Worst-case aaab in aaaaaaab: how many total fallback steps?

4 — one per position

i = 3..6

, each dropping

j

by 1, bounded by

n

For an empty pattern (

m = 0

), what must your code do?

Special-case it — it matches at every position and the loops have nothing to compare.