Z-Function (Z-Algorithm)

This is an extension topic beyond most interviews; it pays off in string questions phrased as "how much of the string's beginning reappears starting here", where it is often simpler to reason about than KMP's prefix function.

Intuition

For a string s of length n, the Z-function stores, for every position i, the length of the longest common prefix of s and the suffix s[i:]:

• z("aaaaa") = [5, 4, 3, 2, 1]
• z("abacaba") = [7, 0, 1, 0, 3, 0, 1]

(z[0] is set to n here; some texts use 0. Pick one and say so.)

Computing each value by brute force is O(n^2). The linear algorithm keeps the Z-box: the window [l, r) with the largest r found so far such that s[l:r] equals the prefix s[0:r - l]. For a new position i inside the box, the text at i is a copy of the text at i - l, so z[i] is at least min(r - i, z[i - l]). Only characters beyond r need fresh comparisons, and every successful comparison pushes r forward. Since r never moves back and is at most n, the total work is O(n).

Compared with the prefix function: pi[i] describes the longest border of the prefix ending at i; z[i] describes the match of the prefix starting at i. They carry the same information and solve the same family of problems; use whichever reads more naturally.

When to use it in interviews / OAs

• Find every occurrence of a pattern: compute z(pattern + separator + text).
• "For every suffix, how long is its common prefix with the whole string?" Sum of scores of built strings is just sum(z).
• "Remove k characters from the front and append anything; when does the word first return to its initial state?": the first multiple t * k whose suffix is also a prefix.
• Periodicity: the smallest p dividing n with p + z[p] == n is the shortest repeating block.
• Prefix/suffix overlaps: s[i:] is a prefix of s exactly when i + z[i] == n.

Template

Z-algorithm

def z_function(s: str) -> list[int]:
    n = len(s)
    z = [0] * n
    l = r = 0  # s[l:r] matches a prefix of s, with r as large as possible
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])  # copy what the mirrored position already knows
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1  # extend beyond the box by direct comparison
        if i + z[i] > r:
            l, r = i, i + z[i]
    if n:
        z[0] = n  # convention: the whole string matches itself
    return z

Pattern matching

def z_search(text: str, pattern: str, sep: str = "\x00") -> list[int]:
    # pattern is non-empty; sep must occur in neither string
    m = len(pattern)
    z = z_function(pattern + sep + text)
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] == m]

Using prefix overlaps

def min_time_to_initial(word: str, k: int) -> int:
    # each second: drop the first k characters, append any k characters
    n, z = len(word), z_function(word)
    t = 1
    while t * k < n and z[t * k] < n - t * k:  # the remaining suffix must be a prefix
        t += 1
    return t


def smallest_full_period(s: str) -> int:
    # length of the shortest block b with s == b * (n // len(b))
    n, z = len(s), z_function(s)
    for p in range(1, n):
        if n % p == 0 and p + z[p] == n:
            return p
    return n

Complexity

z_function is O(n) time and O(n) memory. Matching costs O(n + m). The overlap helpers are O(n) after computing z.

Common pitfalls

• The z[0] convention. Code that sums or scans z must agree on whether z[0] is 0 or n.
• Off-by-one in the box. With a half-open box [l, r), the reuse bound is r - i; with a closed box it is r - i + 1. Mixing the two silently breaks the linear bound or the answer.
• Forgetting to extend. Copying z[i - l] is only a lower bound when it reaches the box edge; you must keep comparing past r.
• Separator collisions. In pattern + sep + text, the separator must not appear in either string, or matches can run across it. "\x00" is a safe choice for normal text.
• Updating the box with a shorter match. Only move [l, r) when i + z[i] > r.

Interview variations

• Find the index of the first occurrence. z_search(text, pattern)[0] (or -1 when empty).
• Sum of scores of built strings. sum(z_function(s)) with the z[0] = n convention.
• Minimum time to revert a word to its initial state. min_time_to_initial above; linear even for n = 10^6.
• Repeated substring pattern / shortest period. smallest_full_period(s) < len(s).
• Longest prefix that is also a suffix. The smallest i with i + z[i] == n gives a border of length n - i.
• Count distinct substrings incrementally. Appending a character adds |t| - max(z_t[1:]) new substrings, where t is the new string reversed and z_t its Z-function; O(n^2) overall, fine for small inputs.