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

Two names we will use from the very first line, so let us fix them now:

Before you can follow the parent derivation, you must own — cold — every piece of notation it throws at you. This page introduces each one from nothing: plain words first, then the picture, then why the topic can't live without it. Read top to bottom; each idea leans on the one above.

1. Strings, characters, and indexing

We need a way to point at one specific bead. That is what indexing does.

Figure 1 (above) draws $S=\text{ababaca}$ as seven boxed beads on a wire, with a small grey number under each box showing its index $0,1,\dots ,6$. An orange arrow points at the leftmost box to remind you it is $S[0]$ (the first bead), and a plum arrow tags the middle box as $S[4]=\text{a}$. The picture matters because every later idea is really "point at these boxes and slice between them" — you must first see that positions are numbered from zero.

Why the topic needs it. KMP is a story about two moving fingers — one on the pattern, one on the text. To say "the finger is here" precisely, we must be able to name each position. $S[k]$ is that naming.

2. Substrings, prefixes, and suffixes

Now we slice pieces out of a string.

Two special substrings drive the whole algorithm: the front chunk and the back chunk.

Figure 2 (above) shows the string $\text{ababa}$ drawn twice. On the top copy the first three boxes are shaded and a teal bracket labels them "proper PREFIX 'aba'" — the front slice $S[\mathrm{0..2}]$. On the bottom copy the last three boxes are shaded with a plum bracket labelled "proper SUFFIX 'aba'" — the back slice $S[\mathrm{2..4}]$. The orange caption between them notes that the very same three letters appear at both ends. The figure matters because "front slice" versus "back slice" is abstract in words but obvious once you literally see the two shaded regions sitting at opposite ends of the same beads.

Why the topic needs it. The failure function asks a question purely about prefixes and suffixes: "how much does the front of my pattern also appear at the back of what I've matched?" Without these two words the definition of $\pi$ cannot even be stated. The word proper is not decoration — the parent note's first steel-man mistake shows that dropping it causes an infinite loop.

3. A border (prefix that is also a suffix)

This is the heart concept the whole cheat-sheet is built from.

Figure 3 (above) overlays two frames on the single string $\text{ababa}$: a solid teal box around the first three beads (the front $\text{aba}$) and a dashed plum box around the last three beads (the back $\text{aba}$). The two frames physically overlap in the middle, which is the visual "aha" — the same three letters are being reused at both ends. The orange caption states the payoff, $\pi [4]=3$. Look at how the boxes share the centre bead: that shared overlap is exactly why sliding the pattern to a border costs nothing to recheck.

Why the topic needs it. $\pi [i]$ is literally "the length of the longest border of $S[\mathrm{0..}i]$." Everything else — the recurrence, the fallback chain, the linear time — is machinery for computing and using borders. See Borders and Periods of Strings for the deeper theory of why borders come in neat nested chains.

4. The failure function $\pi$ and the notation $\pi [i]$

So $\pi$ is not one number; it is a whole row of numbers, computed once, then consulted. Here is the complete table for $S=\text{ababaca}$ — every index $0$ through $6$, none skipped, so you can see what lives in each slot:

Read it as: "at slot $i$, look at the front-piece $S[\mathrm{0..}i]$, find its longest border, and record that border's length." A 0 never means "missing" — it means the only border is the empty string.

Why the topic needs it. $\pi$ is the cheat-sheet itself. Building it is the "preprocessing" half of KMP; reading it during the scan is the "matching" half. When you see $j=\pi [j-1]$ in the parent note, it means "look up slot $j-1$ of the cheat-sheet to find the next border length to try."

5. The two fingers $i$ and $j$

Figure 4 (above) stacks the text $T=\text{ababaab}$ (teal boxes, top) over the pattern $P=\text{abab}$ (plum boxes, bottom). A dotted orange line drops from a text box down to a pattern box to show the two fingers meeting at the current comparison; the top of the line is labelled "text finger $i$" and an arrow into the pattern is labelled "pattern finger $j$ (chars matched so far)". The bold caption states the golden rule: $i$ only moves right, while $j$ rises slowly and falls by borders. The picture matters because the whole speed argument is a claim about how these two fingers are allowed to move, and it is far easier to trust once you have watched them line up.

Why the topic needs it. The entire O(n+m) magic is a statement about these fingers: $i$ never moves backward, and $j$ can only rise slowly but fall by borders. Keeping the two fingers straight is what separates "I read the code" from "I understand the code."

6. Big-O, $n$, $m$, and "linear time"

Why the topic needs it. The parent note's centrepiece is proving KMP is $O(n+m)$, not $O(nm)$. You cannot read that proof without knowing what these symbols promise. The full accounting method lives in Amortized Analysis.

Prerequisite map

This feeds directly into the parent KMP note. Nearby algorithms reuse these same foundations: Z-algorithm and Rabin-Karp are alternative single-pattern matchers, while Aho-Corasick, Suffix Automaton, and Suffix Array scale the ideas to many patterns and whole-text indexing.

Equipment checklist

Cover the right side and answer aloud; reveal to check.