Z-Function

$z[i]$ = the length of the longest common prefix of $s$ and the suffix $s[i..]$. By convention $z[0]=n$ (or 0; be consistent).

s = a a b c a a b x a a a z
z = _ 1 0 0 3 1 0 0 2 2 1 0

Computation — $O(n)$

Maintain the Z-box $[l,r)$: the rightmost interval known to match a prefix of $s$.

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    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]);        // reuse previous work
        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]; }     // extend the Z-box
    }
    return z;
}

Why linear: the while loop only runs when it pushes $r$ further right, and $r$ never decreases — so the total number of character comparisons is $O(n)$.

Why min(r - i, z[i - l]): inside the Z-box, $s[i..r)$ equals $s[i-l..r-l)$, so $z[i]$ starts at $z[i-l]$ — capped at $r-i$, because beyond $r$ nothing is known yet.

Pattern matching

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

$O(n+m)$ time and memory. The separator must not appear in either string.

What the Z-function answers

Question	Method
All occurrences of a pattern	as above
Number of distinct substrings	add characters one at a time, using $z$ of the reversed prefix
Longest common prefix of $s$ and $t$	$z$ of $t+\#+s$
Is $t$ a rotation of $s$?	search $t$ in $s+s$
Smallest period	smallest $p$ with $p+z[p]=n$
Compare $s[i..]$ with $s[j..]$	one $z$ query plus one character
String compression / repeated blocks	check $i$ with $i+z[i]=n$ and $i\mid n$

Counting distinct substrings incrementally

Adding a character to the end of $s$ creates $n$ new substrings (the suffixes of the new string), minus those that already occurred. Computing the Z-function of the reversed new string gives $\max z$, the length of the longest new suffix that already appeared, so the count increases by $n-\max z$. Total $O(n^2)$ — good enough when $n\le 5000$ and much simpler than a suffix structure.

Z-function vs prefix function

They are interconvertible in $O(n)$ and both solve matching in linear time. Practical differences:

	Z-function	Prefix function
Meaning	LCP with the whole string	longest border of a prefix
Easier to derive from scratch	✔
Extends to an automaton		✔
Extends to multi-pattern		✔
Gives periods directly	needs a scan	✔ immediately

Use the Z-function for matching and comparison; the prefix function when you need borders, periods, or an automaton to run a DP over.

The Z-box idea generalises

“Maintain the rightmost known-matching interval and reuse it” is exactly the technique behind Manacher’s algorithm for palindromes. Recognising the shared skeleton makes both easier to remember: keep an interval, reuse the mirrored answer, extend naively only past the boundary.

See also: Prefix Function · Z-Algorithm · Manacher