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

Prerequisite ideas we lean on: Borders and Periods of Strings (a border is a prefix that is also a suffix) and, for the running-time picture, Amortized Analysis. Cousins that solve the same job differently: Z-algorithm, Rabin-Karp. Parent: KMP — full derivation.

Step 1 — What are we even looking at? Prefix, suffix, border

WHAT. Take a string $S$ , say ababa. A prefix is any chunk you get by reading from the left and stopping. A suffix is any chunk you get by reading up to the right end. A border is a chunk that is both — the same characters appear at the start and at the end.

WHY. Everything in KMP is one question: "After I've matched some characters, which of them at the front are secretly a copy of the ones at the back?" That copy is a border. So we must be able to see borders before anything else.

PICTURE. Below, the blue bar is a prefix growing from the left; the orange bar is a suffix growing from the right. Where a blue chunk and an orange chunk hold the exact same letters, we have a border (green). aba is a border of ababa: front aba = back aba.

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

Step 2 — Why a border is exactly what a mismatch needs

WHAT. Line the pattern $P$ up under the text $T$ . Recall from the definitions above that $j$ = the current length of the matched prefix. Suppose the first $j$ characters of $P$ matched, and then character $P [j]$ disagrees with the text character $T [i]$ .

WHY. We refuse to move the text pointer $i$ backwards. But the pattern must slide right to try again. How far? Look at what we already know: the last $j$ text characters we scanned are equal to the first $j$ pattern characters (that's what "matched" means). If the front of the pattern reappears at the back of that matched run — a border! — then sliding the pattern so its front lands on that border needs no re-reading: those characters already agree.

PICTURE. The green matched run is the same on top (text $T$ ) and bottom (pattern $P$ ). The longest border of that run (darker green) is the only slide that keeps us honest: shorter would re-check nothing new, longer would skip a possible match.

Step 3 — Reading π off `ababaca` by eye

WHAT. Compute $π$ for the string $S =$ ababaca, position by position, purely by spotting the longest green border.

WHY. Before we automate it, you must trust that $π$ is just "measure the longest border here." Automation is only a fast way to do exactly this.

PICTURE. Each row grows the string by one letter. The green bar shows the longest proper border found; its length is $π [i]$ .

$i$	prefix $S [0.. i]$	longest proper border	$π [i]$
0	`a`	(none)	0
1	`ab`	(none)	0
2	`aba`	`a`	1
3	`abab`	`ab`	2
4	`ababa`	`aba`	3
5	`ababac`	(none, ends in `c`)	0
6	`ababaca`	`a`	1

Each symbol: $i$ = how far right we've read; $π [i]$ = the green length. At $i = 5$ the string ends in c, and no front chunk of ababac ends in c, so the border vanishes to $0$ .

Step 4 — Building π: the "extend" move (Case 1)

WHAT. Suppose we already know the answer one step back: let $j = π [i - 1]$ , the best border length for the previous prefix. Now we add character $S [i]$ . If $S [i]$ equals $S [j]$ , the border grows by one on both ends at once.

WHY. A border of length $j$ means "first $j$ chars = last $j$ chars." The character sitting just after that front copy is $S [j]$ . The new character we just appended is $S [i]$ . If they're equal, we can stretch both the front copy and the back copy by one letter — a longer border. So $π [i] = j + 1$ .

PICTURE. The green border of length $j$ is flanked by two equal letters (the one at index $j$ in front, the one at index $i$ at the back). Matching them zips the border up to length $j + 1$ .

Step 5 — Building π: the "fall back" move (Case 2)

WHAT. Now $S [i] \neq = S [j]$ and $j > 0$ . We cannot extend. Instead of scanning from scratch, we jump $j \leftarrow π [j - 1]$ and try again.

WHY. We wanted a border of length $j$ to extend, but the follow-up letter didn't match. The next candidate must be a shorter border of the same matched run — and the longest border shorter than $j$ is precisely the longest border of that border, which is stored at $π [j - 1]$ . So we walk down a chain of nested borders, each one the border of the last, until either the letters match (extend) or we hit $j = 0$ .

PICTURE. A ladder of shrinking green borders: length $j$ , then $π [j - 1]$ , then $π [π [j - 1] - 1]$ , … Each rung is the border of the rung above. We stop at the first rung whose next character matches $S [i]$ .

Step 6 — Degenerate case: bottomed out (Case 3)

WHAT. The fall-back chain can reach $j = 0$ . If $S [i]$ still doesn't match $S [0]$ , there is no border at all — set $π [i] = 0$ and move on.

WHY. $j = 0$ means "no matched front left to reuse." At that point the only question is whether the new letter equals the very first letter $S [0]$ : if yes, $π [i] = 1$ ; if no, $π [i] = 0$ . There is nothing below zero — this is the floor that guarantees the loop always stops.

PICTURE. The green ladder has hit the ground. Two outcomes: new letter equals $S [0]$ (tiny green border of length 1) or it doesn't (bare zero).

Step 7 — Why the whole thing is O(n+m): watch j, not i

WHAT. Run the matcher across the text $T$ (length $n$ ). Track a single quantity: the value of $j$ (how many pattern characters are currently matched).

WHY. Two facts about $j$ :

The text loop runs $n$ times, and each pass raises $j$ by at most 1 (j += 1). So over the whole run, $j$ goes up by at most $n$ .
Every fall-back step (j = π[j-1]) lowers $j$ by at least 1 (a proper border is strictly shorter). Since $j \geq 0$ always, it can't fall more than it rose. So total fall-back steps $\leq$ total rises $\leq n$ . The inner while runs $n$ times across the entire run, not per character.

PICTURE. A staircase: $j$ climbs one step at a time (blue up-arrows) and occasionally plunges (orange down-arrows). The total drop can never exceed the total climb — that's the amortized bound. (See Amortized Analysis for this "potential" style of argument.)

Recall Where do the two terms

$n$ and $m$ come from? $n$ ::: the matching loop over the text $T$ : text pointer $i$ moves forward $n$ times, total fall-backs $\leq n$ . $m$ ::: the identical staircase argument while building $π$ over the pattern $P$ of length $m$ .

Step 8 — The machine in motion: pattern $P =$ `abab`, text $T =$ `ababaababab`

WHAT. Watch the derived rules run on a real search. Here $S$ from Steps 1–6 becomes the pattern $P =$ abab, so $π$ for $P$ is $[0, 0, 1, 2]$ . We slide $P$ under the text $T$ ; on a full match ( $j$ reaches $m = 4$ ) we report the start index and set $j = π [m - 1]$ to catch overlapping matches.

WHY. This is where Steps 4–6 pay off: at text index $i = 5$ a mismatch fires the fall-back ladder $j : 3 \to 1 \to 0 \to$ match, reusing the single a instead of restarting — exactly the border logic, live.

PICTURE. The pattern $P$ (blue) sitting under the text $T$ (gray). Green cells = matched, red cell = the mismatch that triggers a slide. The reported overlapping matches start at text indices $0$ , $6$ , and $7$ .

$i$	$T [i]$	$j$ before	what happens	$j$ after
3	b	3	match → $j = 4 = m$ , report start 0, $j = π [3] = 2$	2
5	a	3	mismatch: $j = π [2] = 1$ , then $π [0] = 0$ , then `a`=`a`	1
7	b	3	match → $j = 4$ , report start 4, $j = 2$	2
9	b	3	match → $j = 4$ , report start 6, $j = 2$	2

Matches start at text indices $0, 4, 6$ — the last two overlap, which is only possible because we set $j = π [m - 1]$ (not $0$ ) after a hit.

The one-picture summary

Everything above collapses into one diagram: a border of the matched run is the only safe slide, and $π$ pre-measures it so the text pointer $i$ never retreats.

In the flowchart below, remember: $T$ = text, $P$ = pattern, $i$ = text index (forward only), $j$ = matched-prefix length, $m$ = pattern length, and $π$ = the failure function we built in Steps 1–6.

Recall Feynman retelling of the whole walkthrough

You're checking whether a small word (the pattern $P$ ) hides inside a big book (the text $T$ ), reading the book left to right and never going back. You match letters until one slips. A dumb reader would restart the word from its first letter at the next book position. The smart reader notices something: "the last few letters I just matched are the same letters my word starts with." That repeated chunk — same at the front and the back — is a border. Instead of restarting, the reader slides the word so its front lands exactly on that border; those letters already agree, so no re-reading. The cheat-sheet $π$ says, for every spot in the word, how long that reusable border is. Building the cheat-sheet is the same trick applied to the word against itself: extend the border when the next letter matches, and drop to the border-of-the-border when it doesn't. Because the "matched count" $j$ can only fall as much as it climbed, and it climbs at most once per book letter, the whole search finishes in time proportional to book + word — that's $O (n + m)$ .