A Pattern Carries Its Own Restart Points

A built prefix function is not a search result. It does not say where a string occurs in a text. It only describes the pattern’s internal self-overlap: which beginnings of the pattern reappear as endings of its own prefixes.

That is exactly the information needed by the Knuth–Morris–Pratt algorithm. When a match attempt fails, KMP asks: “How much of the pattern’s beginning have I already seen at the end of what matched?” The prefix function answers that question without looking backwards in the text.

The table is about the pattern alone

For $P=\mathrm{ababaca}$, the prefix function is built before the text is scanned.

Each entry $\pi (q)$ talks only about the prefix $P[\mathrm{0..}q]$. It gives the length of the longest proper string border of that prefix.

So $\pi (4)=3$ means:

$$P[\mathrm{0..4}]=\mathrm{ababa}$$

has longest proper border $\mathrm{aba}$, whose length is $3$.

The value says what survives a mismatch

Suppose a search has matched $\mathrm{ababa}$, so the current matched length is $q=5$. The next comparison fails. The whole five-character match cannot be kept, because its next character was wrong.

But the suffix $\mathrm{aba}$ of the matched text is also the prefix $\mathrm{aba}$ of the pattern. That part can survive. The table says this directly:

$$q\leftarrow \pi (q-1)=\pi (4)=3.$$

This is the important shift in viewpoint: $q$ is not “where the pattern is in the text”. It is “how much of the pattern’s beginning is currently alive”. After a mismatch, the prefix function tells how much remains alive.

One entry can hide a whole chain

The value $\pi (q-1)$ is the first fallback. If the same text character still does not match, KMP follows the same idea again.

For $P=\mathrm{ababaca}$, after matching length $5$:

$$5\to \pi (4)=3\to \pi (2)=1\to \pi (0)=0.$$

These are not random jumps. They are the possible border lengths of the already matched prefix, tried from longest to shortest.

So the built prefix function is a map of possible recoveries. It tells KMP: if the current guess is too long, which shorter guess is still consistent with the characters already seen?

What to remember

The prefix function tells you how the pattern can restart inside itself.

It turns a failed comparison from “start over” into “keep the longest part that is still justified”. That is why KMP can move through the text without backtracking: the text scan supplies the characters, and the prefix table supplies the safe fallback lengths.