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

---

The scenario matrix

Every string the failure function can face falls into one of these case classes. The examples below hit every cell.

#	Case class	What makes it special	Example
A	Generic pattern (mixed borders)	$\pi$ rises and falls, normal fallback chain	Ex 1
B	All-identical characters aaaa	$\pi$ climbs $0,1,2,3$ — maximal borders	Ex 2
C	No border at all abcd	$\pi$ stays $0$ everywhere — worst reuse	Ex 3
D	Nested / chained borders	one mismatch falls back through several $\pi$ slots	Ex 4
E	Degenerate inputs — length-1 pattern, empty pattern, empty text	$\pi [0]=0$; $m=0$ and $n=0$ edges	Ex 5
F	Overlapping matches	full match, then continue via $\pi [m-1]$ not $0$	Ex 6
G	No match exists	text pointer marches, $j$ never reaches $m$	Ex 7
H	Amortized limit (adversarial)	the $O(nm)$-killer input, proving linearity	Ex 8
I	Real-world word problem	applied framing	Ex 9
J	Exam twist — smallest period from $\pi$	using $\pi [m-1]$ for a different question	Ex 10

---

Example 1 — Generic pattern (Cell A)

Forecast: Guess: does $\pi$ reach $3$ before dropping? Where does it drop to $0$?

1. $i=0$: $\pi [0]=0$ by definition (single char, no proper prefix). Why this step? Every build starts here — it is the base case of the recurrence.
2. $i=1$ (b): j=pi[0]=0; S[1]=b, S[0]=a, mismatch, j=0 already → $\pi [1]=0$ (Case 3). Why? No prefix of ab is also a suffix.
3. $i=2$ (c): j=0; c≠a → $\pi [2]=0$ (Case 3). Why? With j=0 we compare the new char c to the very first char a; they differ and $j$ is already $0$, so no prefix of abc is a suffix — border length stays $0$.
4. $i=3$ (a): j=pi[2]=0; S[3]=a, S[0]=a match → j=1, $\pi [3]=1$ (Case 1). Why? The prefix a now reappears as a suffix of abca.
5. $i=4$ (b): j=pi[3]=1; S[4]=b, S[1]=b match → j=2, $\pi [4]=2$ (Case 1). Why? Border ab grew from border a by one matching char.
6. $i=5$ (c): j=2; S[5]=c, S[2]=c match → j=3, $\pi [5]=3$ (Case 1). Why? The border was ab (length 2); the new char c equals S[2]=c, so the border extends by one to abc (length 3) — Case 1 firing a third time in a row.
7. $i=6$ (d): j=3; S[6]=d, S[3]=a mismatch → j=pi[2]=0 (Case 2); d≠a → $\pi [6]=0$ (Case 3). Why? d breaks every border; we fall to the bottom.

Answer: $\pi =[0,0,0,1,2,3,0]$.

Verify: $S[\mathrm{0..5}]=$abcabc has longest proper prefix=suffix abc (length 3) ✓; adding d kills all borders ✓.

---

Example 2 — All-identical characters (Cell B)

Forecast: Will $\pi$ be $0,1,2,3$ or something smaller?

1. $i=0$: $\pi [0]=0$.
2. $i=1$: j=0; a==a → j=1, $\pi [1]=1$ (Case 1). Why? Prefix a = suffix a of aa. Proper (length 1 < 2). ✓
3. $i=2$: j=pi[1]=1; S[2]=a, S[1]=a match → j=2, $\pi [2]=2$ (Case 1). Why? The previous border was a (length 1); the new char equals S[1]=a, so the border extends to aa (length 2).
4. $i=3$: j=pi[2]=2; S[3]=a, S[2]=a match → j=3, $\pi [3]=3$ (Case 1). Why? Border aa (length 2) extends by the matching char S[2]=a to aaa (length 3); still proper because $3<4$.

Answer: $\pi =[0,1,2,3]$.

Verify: For aaaa, the longest proper prefix that is a suffix is aaa (length $m-1=3$) — never $4$, because proper forbids the whole string. This is exactly why we insist on proper in the definition: allowing the whole string would give $\pi [i]=i+1$ everywhere and the fallback j=pi[j-1] would never shrink $j$, causing an infinite loop.

---

Example 3 — No border anywhere (Cell C)

Forecast: What does $\pi$ look like when nothing ever repeats?

1. $\pi [0]=0$.
2. $i=1$: j=pi[0]=0; S[1]=b, S[0]=a, b≠a → $\pi [1]=0$ (Case 3). Why? j is already $0$ and the new char b differs from the first char a, so no prefix of ab is a suffix — border stays $0$.
3. $i=2$: j=pi[1]=0; S[2]=c, S[0]=a, c≠a → $\pi [2]=0$ (Case 3). Why? Same situation: c differs from the first char a, so abc has no prefix=suffix.
4. $i=3$: j=pi[2]=0; S[3]=d, S[0]=a, d≠a → $\pi [3]=0$ (Case 3). Why? d differs from a; abcd has no repeated character, so no border can exist.

Answer: $\pi =[0,0,0,0]$.

Verify: No character repeats, so no prefix can equal any suffix — $\pi$ is all zeros. On a mismatch, matching such a pattern behaves exactly like naive (nothing to reuse), yet still $O(n)$ because $i$ never rewinds. See Borders and Periods of Strings for the border-free case.

---

Example 4 — Nested border chain (Cell D)

Forecast: At the last char, how many times does the while loop fire?

1. $\pi [0]=0$. Why? Base case — a single char a has no proper prefix.
2. $i=1$ (a): j=pi[0]=0; a==a → $\pi [1]=1$ (Case 1). Why? The new char a equals the first char S[0]=a, so aa has border a (length 1).
3. $i=2$ (b): j=pi[1]=1; S[2]=b, S[1]=a mismatch → j=pi[0]=0 (Case 2); b≠a → $\pi [2]=0$ (Case 3). Why? The border a cannot extend (b≠a), so we fall back to $\pi [0]=0$; still no match, so border length is $0$.
4. $i=3$ (a): j=pi[2]=0; a==a → $\pi [3]=1$ (Case 1). Why? With j=0, the new char a equals S[0]=a, restarting a border of length 1 for aaba.
5. $i=4$ (a): j=pi[3]=1; S[4]=a, S[1]=a match → $\pi [4]=2$ (Case 1). Why? Border a (length 1) extends by the matching char S[1]=a to aa (length 2).
6. $i=5$ (a): j=pi[4]=2; S[5]=a, S[2]=b mismatch → j=pi[1]=1 (Case 2); S[5]=a, S[1]=a match → $\pi [5]=2$ (Case 1). Why the fallback? Border of length 2 couldn't extend (b≠a), so we asked "what is the longest border inside that border?" — $\pi [1]=1$ — and tried again. This is the border chain walking down (Case 2).
7. $i=6$ (b): j=pi[5]=2; S[6]=b, S[2]=b match → $\pi [6]=3$ (Case 1). Why? Border aa (length 2) extends by the matching char S[2]=b to aab (length 3).

Answer: $\pi =[0,1,0,1,2,2,3]$.

Verify: aabaaab — longest proper prefix=suffix is aab (length 3): prefix aab = last three chars aab ✓. Step 6 fired the while once (Case 2) then matched (Case 1) — the chained fallback in action.

---

Example 5 — Degenerate inputs (Cell E)

Forecast: Can a single character have a border? How many matches does an empty pattern have?

1. Length-1 pattern x: $\pi [0]=0$ by definition — a single char has no proper prefix (the only prefix is the whole thing, which is forbidden). Why? Proper prefix must be strictly shorter; nothing shorter than length 1 except the empty string, which gives border length 0.
2. Empty pattern ($m=0$): the build loop for i=1..m-1 never runs; $\pi$ is the empty array. In matching, j==m is j==0 — a match is reported at every position (the empty string occurs everywhere). Guard this in code with an explicit if m==0 to avoid reading pi[m-1]=pi[-1]. Why care? Contest judges love empty-input edge cases; forgetting the guard gives out-of-range reads.
3. Empty text ($n=0$): the match loop for i=0..n-1 never runs, so $j$ stays $0$. Result: zero matches for any non-empty pattern — correct, since nothing can occur in nothing. (If $m=0$ too, conventions differ; most define the empty pattern to match once, at position 0.) Why mention it? It is the mirror image of the empty pattern — the degenerate case on the text side, and it must not crash: an empty loop simply produces an empty match list.

Answer: $\pi (\text{x})=[0]$; empty pattern → matches everywhere; empty text → no matches (for non-empty $P$).

Verify: For x, longest proper prefix=suffix length is $0$ ✓. Searching any pattern in an empty text yields $[]$ ✓.

---

Example 6 — Overlapping matches (Cell F)

Forecast: How many matches — 2 or 3? (Naive-reset thinking says 2.)

First, $\pi (\text{aa})=[0,1]$ and $m=2$.

$i$	$T[i]$	$j$ before	action	$j$ after
0	a	0	match → j=1	1
1	a	1	match → j=2=m, report $1-2+1=0$, j=pi[1]=1	1
2	a	1	match → j=2=m, report $2-2+1=1$, j=1	1
3	a	1	match → j=2=m, report $3-2+1=2$, j=1	1

Why this step (the j=pi[m-1] on match)? After reporting, we keep the overlap a (length $\pi [1]=1$) instead of throwing it away, so the next a completes the next overlapping match. Resetting j=0 would drop the overlap and miss matches.

Answer: matches at indices $\{0,1,2\}$ — three overlapping aa.

Verify: aaaa contains aa starting at 0,1,2 ✓. Resetting j=0 would have missed indices 1 and 2 — this is why a full match continues via $\pi [m-1]$, not $0$.

---

Example 7 — No match exists (Cell G)

Forecast: Does $j$ ever reach $3$?

$\pi (\text{abx})=[0,0,0]$, $m=3$.

$i$	$T[i]$	$j$ before	action	$j$ after
0	a	0	a==a → j=1	1
1	b	1	b==b → j=2	2
2	a	2	P[2]=x≠a, j=pi[1]=0; a==a → j=1	1
3	b	1	b==b → j=2	2
4	a	2	x≠a, j=0; a==a → j=1	1
5	b	1	b==b → j=2	2

Why does $i$ still march forward on every mismatch? Because the reused prefix P[0..π[j-1]-1] is already known equal to the text — re-reading it is wasted work. $j$ tops out at $2$, never $3$.

Answer: no matches; $j$ never reaches $m=3$.

Verify: abx does not occur in ababab ✓ (no x). Total text reads = 6, one per char — linear even with zero matches.

---

Example 8 — Adversarial amortized limit (Cell H)

Forecast: How many inner-while steps fire in total across the whole run?

$\pi (\text{aaab})=[0,1,2,0]$, $m=4$, $n=8$.

The interesting positions: while the text feeds a, $j$ climbs $0\to 1\to 2\to 3$. Let us count the amortized budget instead of every row:

1. Total j increases $\le n=8$ (at most one +1 per text char). Why? The if T[i]==P[j] line runs once per $i$.
2. Total while decreases $\le$ total increases $=8$, since $j\ge 0$ always and each while step drops $j$ by $\ge 1$. Why? $j$ behaves like a bank account: deposits $\le 8$, so withdrawals $\le 8$.
3. Therefore inner steps across the entire scan are $\le 8$, not $8\times 4$.

Running it, the single match is aaab: the b is at index 7, and aaab ends there, starting at $7-4+1=4$.

Answer: one match at index $4$; total inner-while steps $\le 8$ → runtime $O(n+m)$, not $O(nm)$. See Amortized Analysis.

Verify: aaaaaaab[4:8] $=$ aaab $=P$ ✓; and no earlier start works because a match needs the b.

---

Example 9 — Real-world word problem (Cell I)

Forecast: Overlaps again — 1 hit or 2?

$\pi (\text{ATA})=[0,0,1]$, $m=3$.

$i$	$T[i]$	$j$ before	action	$j$ after
0	A	0	match → j=1	1
1	T	1	match → j=2	2
2	A	2	match → j=3=m, report $0$, j=pi[2]=1	1
3	T	1	match → j=2	2
4	A	2	match → j=3=m, report $2$, j=1	1
5	T	1	match → j=2	2

Why report 0 and 2? The overlap A (length $\pi [2]=1$) is preserved after each hit, so the next TA completes the following motif. A gene aligner must catch overlaps — biology does not care that they share a base.

Answer: motif ATA starts at indices $\{0,2\}$.

Verify: ATATAT[0:3]=ATA ✓, ATATAT[2:5]=ATA ✓, no start at index 4 (only AT remains).

---

Example 10 — Exam twist: smallest period from $\pi$ (Cell J)

Forecast: Is the answer 3? Or 9 (no repetition)?

1. Build the last $\pi$ value. By the same climb as Ex 1, abcabcabc has $\pi [8]=6$ (longest proper prefix=suffix is abcabc). Why $6$? The first 6 chars abcabc equal the last 6 abcabc.
2. Apply the period formula. $p=m-\pi [m-1]=9-6=3$. Why does this work? A border of length $\pi [m-1]$ means the string, shifted right by $m-\pi [m-1]$, still lines up with itself on the overlapping region. A shift that leaves the string aligned with itself is precisely a period. So the smallest such shift, $p=m-\pi [m-1]$, is the smallest period candidate. See Borders and Periods of Strings.
3. Check the divisibility condition $p\mid m$. Here $p=3$ and $m=9$, and $9\mathrm{mod}3=0$, so $3\mid 9$. This is what upgrades $p$ from "a shift that aligns" to "the string is exactly $\frac{m}{p}=3$ full copies of the block abc." If $p$ did not divide $m$ (say the string were abcabca, $m=7$, $\pi [6]=4$, $p=3$, but $7\mathrm{mod}3\ne 0$), the string would be only partially periodic — the last block is a fragment — and the smallest full period would be $m$ itself. Why check it at all? Because the question asks for a period that tiles $S$ completely; without $p\mid m$ the block does not tile, so the answer must fall back to $m$.

Answer: smallest period $p=3$ (abc repeated three times), and since $3\mid 9$ this is a genuine full period.

Verify: $9-6=3$, $9\mathrm{mod}3=0$ ✓; abc×3 = abcabcabc ✓. Counter-check: abcabca gives $p=3$ but $7\mathrm{mod}3\ne 0$, so it is not fully periodic ✓.

---

Recall Which cell was hardest?

The nested chain (Ex 4) and the overlap trap (Ex 6). If you can do those two cold, the rest are routine. Which example proves linearity? ::: Example 8 — the adversarial aaaaaaab amortized count. Which formula did the exam twist use? ::: smallest full period $=m-\pi [m-1]$ when it divides $m$.

Active Recall