Prefix Function (KMP)

$\pi [i]$ = the length of the longest proper border of $s[\mathrm{0..}i]$ — a string that is both a proper prefix and a suffix of that prefix.

$\pi [i]=\max \{k<i+1:s[\mathrm{0..}k)=s[i-k+\mathrm{1..}i]\}.$

Computation — $O(n)$

vector<int> prefixFunction(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];    // fall back along borders
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

Why it is linear: $j$ increases by at most 1 per iteration ($n$ total increases) and the while loop only decreases it, so the total number of decreases is also $O(n)$. The same amortization as Kasai and the monotonic stack.

Pattern matching

Run the prefix function on pattern + '#' + text, where # occurs in neither. Every position where $\pi =|pattern|$ marks an occurrence.

vector<int> findAll(const string& text, const string& pat) {
    string s = pat + '\x01' + text;
    vector<int> pi = prefixFunction(s), res;
    for (int i = pat.size() + 1; i < (int)s.size(); i++)
        if (pi[i] == (int)pat.size())
            res.push_back(i - 2 * pat.size());
    return res;
}

The separator is essential — without it, $\pi$ could exceed $|pattern|$ and match across the boundary.

Memory-light alternative: run the matching loop directly against the text without concatenating, keeping only the pattern’s $\pi$ array. That is the classic KMP formulation; see KMP.

What $\pi$ gives you

Question	Answer
Smallest period of $s$	$n-\pi [n-1]$
Is $s$ a repetition of a shorter string?	$p=n-\pi [n-1]$ divides $n$ and $p<n$
All borders of $s$	the chain $\pi [n-1],\pi [\pi [n-1]-1],\dots$
Occurrences of a pattern	as above
Number of occurrences of each prefix in $s$	count backwards over $\pi$ (see below)
Shortest string with $s$ as both a prefix and a suffix	$s+s[\pi [n-1]..n)$
Minimum characters to append to make $s$ a palindrome	$\pi$ of $s+\#+\mathrm{reverse}(s)$

Counting prefix occurrences

vector<int> cnt(n + 1, 0);
for (int i = 0; i < n; i++) cnt[pi[i]]++;
for (int i = n - 1; i > 0; i--) cnt[pi[i-1]] += cnt[i];   // propagate along borders
for (int i = 0; i <= n; i++) cnt[i]++;                    // each prefix occurs as itself
// cnt[len] = number of occurrences of the prefix of length len

The KMP automaton

Precompute $\mathrm{aut}[i][c]$ = the state after reading character $c$ in state $i$. That turns matching into a table lookup per character, and — more importantly — makes the pattern into a DFA you can run a DP over.

vector<array<int,26>> aut(n + 1);
for (int i = 0; i <= n; i++)
    for (int c = 0; c < 26; c++) {
        if (i > 0 && c != s[i] - 'a') aut[i][c] = aut[pi[i-1]][c];
        else aut[i][c] = i + (c == s[i] - 'a');
    }

This is the key to problems like “count strings of length $L$ that do not contain the pattern” — a DP over (position, automaton state), often combined with matrix exponentiation when $L$ is huge.

Prefix function vs Z-function

	Prefix function	Z-function
$\pi [i]$ / $z[i]$ means	longest border of the prefix ending at $i$	longest common prefix of $s$ and $s[i..]$
Natural for	periods, borders, automata	pattern matching, string comparison
Conversions	each is computable from the other in $O(n)$

Both are $O(n)$ and both solve pattern matching. Learn one well; the Z-function is slightly easier to reason about, the prefix function extends to automata and Aho-Corasick.

See also: Z-Function · KMP · String Fundamentals