the prefix (failure) function

Some words fold back on themselves. In "ababab", the beginning "abab" reappears at the end; in "aaaa", every prefix is also a suffix. The prefix function measures exactly this self-overlap. For each position in the pattern it records: how long is the longest stretch at the start of the pattern that also appears, identically, ending right here? This single table is the engine that powers the KMP algorithm.

Formally, for a pattern P, the prefix function pi[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i] ('proper' means not the whole thing). For P = "ababaca": pi[0]=0 (a single character has no proper border), pi[1]=0 ("ab"), pi[2]=1 ("aba": the leading "a" matches the trailing "a"), pi[3]=2 ("abab": "ab" reappears), pi[4]=3 ("ababa": "aba" reappears), pi[5]=0 ("ababac"), pi[6]=1 ("ababaca"). It is computed in O(m) by a beautiful self-referential loop: to extend a known border by one character, you try to match the next character against P[pi-so-far]; if it fails you fall back to pi of that position and try again — the function is used to compute itself. The reason it falls back rather than restarts is the same insight as KMP's, applied to the pattern matching against itself.

Why does KMP trust this number? Suppose KMP has matched the first k characters of the pattern and the (k+1)-th mismatches. Any shift that skips over a position where pattern-prefix-equals-matched-suffix could miss a real occurrence; pi[k-1] is precisely the longest such overlap, so shifting to realign it is the largest safe shift. Thus the prefix function is not a heuristic — it is provably the exact amount KMP may advance. The same array also instantly solves related puzzles: counting how many times a string's borders nest, finding the shortest period of a string, and checking if a string is a repetition of a smaller block.