iii. Prefix Function and Z-Function

Two linear-time arrays that answer most single-pattern questions. The prefix function $\pi [i]$ is the length of the longest proper border of $s[\mathrm{0..}i]$ (a proper prefix that is also a suffix); the Z-function $z[i]$ is the length of the longest common prefix of $s$ and $s[i..)$. Both match a pattern in $O(n+m)$; $\pi$ also gives borders, periods and the KMP automaton (the DFA for “contains the pattern”, the basis of Aho–Corasick).

Question	Answer
all occurrences of $p$ in $t$	KMP (streaming, only $\pi$ of $p$ in memory), or $\pi$ / $z$ of $p+\#+t$
smallest period of $s$; is $s$ a power of a shorter string	$n-\pi [n-1]$; that period divides $n$ and is $<n$ (String Basics)
all borders / all periods	the chain $\pi [n-1],\pi [\pi [n-1]-1],\dots$
occurrences of every prefix of $s$ in $s$	count $\pi$ values and propagate along borders
shortest string with $s$ as prefix and suffix	$s+s[\pi [n-1]..n)$
fewest characters to append to make $s$ a palindrome	$n-\pi$ of $\mathrm{rev}(s)+\#+s$ at the end
strings of length $L$ avoiding $p$	DP over the KMP automaton (matrix power for huge $L$)
LCP of $s$ and every suffix; is $t$ a rotation of $s$	$z$; search $t$ in $s+s$
smallest period via $z$	smallest $p$ with $p+z[p]=n$
distinct substrings incrementally	each appended character adds $n-\max z(\mathrm{rev})$ new substrings

	prefix function	Z-function
meaning	longest border of the prefix ending at $i$	LCP of $s$ with $s[i..)$
natural for	periods, borders, automata, multi-pattern	matching, comparisons
conversion	$z\to \pi$ in $O(n)$ (zToPi); both from the string in $O(n)$

vector<int> prefixFunction(const string& s) {
    int n = sz(s); 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;
}
vector<int> kmpSearch(const string& text, const string& pat) {   // start positions, streaming over the text
    vector<int> res; if (pat.empty()) return res;
    vector<int> pi = prefixFunction(pat); int j = 0;
    for (int i = 0; i < sz(text); i++) {
        while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
        if (text[i] == pat[j]) j++;
        if (j == sz(pat)) res.push_back(i - j + 1), j = pi[j - 1];
    }
    return res;
}
vector<int> prefixOccurrences(const string& s) {            // cnt[len] = #occurrences of s[0, len) in s, len = 0..n
    int n = sz(s); vector<int> pi = prefixFunction(s), 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];
    for (int i = 0; i <= n; i++) cnt[i]++;
    return cnt;
}
vector<array<int, 26>> kmpAutomaton(const string& s) {      // aut[state][c], states 0..n (n = full match), lowercase
    int n = sz(s); vector<int> pi = prefixFunction(s); vector<array<int, 26>> aut(n + 1);
    for (int i = 0; i <= n; i++) for (int c = 0; c < 26; c++) {
        if (i < n && c == s[i] - 'a') aut[i][c] = i + 1;
        else aut[i][c] = i == 0 ? 0 : aut[pi[i - 1]][c];
    }
    return aut;
}
vector<int> zFunction(const string& s) {
    int n = sz(s); vector<int> z(n, 0); if (n) z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
    return z;
}
vector<int> zSearch(const string& text, const string& pat) {   // separator '\1' must occur in neither string
    string s = pat + '\1' + text; vector<int> z = zFunction(s), res;
    for (int i = sz(pat) + 1; i < sz(s); i++) if (z[i] >= sz(pat)) res.push_back(i - sz(pat) - 1);
    return res;
}
vector<int> zToPi(const vector<int>& z) {                   // O(n)
    int n = sz(z); vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) for (int j = z[i] - 1; j >= 0 && !pi[i + j]; j--) pi[i + j] = j + 1;
    return pi;
}
string shortestPalindromeByAppending(const string& s) {     // append the fewest characters on the right
    string r(s.rbegin(), s.rend()); vector<int> pi = prefixFunction(r + '\1' + s);
    int keep = pi.back();                                   // longest palindromic suffix of s
    string add = s.substr(0, sz(s) - keep); reverse(all(add));
    return s + add;
}
ll distinctSubstringsIncremental(const string& s) {         // O(n^2) via z of reversed prefixes
    ll total = 0; string cur;
    for (char c : s) {
        cur += c; string rv(cur.rbegin(), cur.rend()); vector<int> z = zFunction(rv);
        int mx = 0; for (int i = 1; i < sz(rv); i++) mx = max(mx, z[i]);
        total += sz(cur) - mx;
    }
    return total;
}

Proof: prefix function, KMP, automaton, Z-function and the applications

Borders nest. If $u$ and $v$ are borders of $w$ with $|u|<|v|$, then $u$ is a border of $v$. Hence the borders of $s[\mathrm{0..}i]$ are exactly $\pi [i],\pi [\pi [i]-1],\dots$, and a border of $s[\mathrm{0..}i]$ of length $k+1$ is a border of length $k$ of $s[\mathrm{0..}i-1]$ extended by $s[i]=s[k]$; trying the candidates $j=\pi [i-1],\pi [j-1],\dots$ in decreasing order finds the longest. Linear time: $j$ grows by at most 1 per step and every fallback decreases it, so the total number of fallbacks is $<n$. KMP search maintains $j$ = the longest prefix of pat that is a suffix of the text read so far (same argument), reports a match when $j=m$, and continues from the longest proper border. Prefix occurrences: an occurrence of $s[\mathrm{0..}k)$ ending at $i$ means $k$ is in the border chain of $s[\mathrm{0..}i]$ (or $k=i+1$); counting $\pi [i]$ and pushing counts down the chain ($\pi [k-1]$ is the next border below $k$) counts each chain element once, plus the prefix itself. Automaton: from state $i$ on $c$, the new state is the longest prefix of $s$ that is a suffix of $s[\mathrm{0..}i)c$: $i+1$ if $c=s[i]$, otherwise the transition of the longest proper border $\pi [i-1]$ on $c$ (computed earlier since $\pi [i-1]<i$), and 0 from state 0.

Z-function. If $i<r$ with $s[l..r)=s[\mathrm{0..}r-l)$, then $s[i..r)=s[i-l..r-l)$, so $z[i]\ge \min (r-i,z[i-l])$ and comparisons need only start beyond that; every successful comparison increases $r$, so the total work is $O(n)$. Conversion $z\to \pi$: a Z-box $[i,i+z_i)$ certifies borders ending at $i+j$ of length $j+1$; for a fixed end the largest such value comes from the leftmost box covering it, so filling from the right end of each box and stopping at already-filled positions assigns each position its maximum once, in total $O(n)$. Palindrome by appending: $\mathrm{rev}(s)\#s$ has, at its end, the longest prefix of $\mathrm{rev}(s)$ equal to a suffix of $s$, i.e. the longest palindromic suffix of $s$; the rest must be mirrored. Distinct substrings: appending $c$ creates the $|cur|$ suffixes as new candidates; the longest one that already occurred is ${\max }_{i\ge 1}z(\mathrm{rev})[i]$, and all shorter suffixes occurred too. Everything was checked against brute force on random strings over small alphabets.

Related notes

• Trie and Aho–Corasick (the multi-pattern automaton)
• Palindromes (Manacher reuses the Z-box idea)
• Matrix Exponentiation DP