Z-Algorithm and Its Invariants

What the Z-Array Measures

For a string $S$ of length $n$, $Z[i]$ is the length of the longest prefix of $S$ that matches the suffix beginning at $i$: $Z[i]=\max\{k\mid S[0\dots k)=S[i\dots i+k)\}$. This document uses the common convention $Z[0]=0$; an implementation using $Z[0]=n$ is also valid if its consumers agree.

A value $Z[i]=k$ means $S[i\dots i+k)=S[0\dots k)$, and either the following symbols differ or one interval reaches the end. For $S=\text{"aabcaabxaaaz"}$, the complete array is $[0,1,0,0,3,1,0,0,2,2,1,0]$.

The Z-Box Invariant

Maintain the half-open interval $[l,r)$ with the greatest right endpoint among prefix matches already discovered, so $S[l\dots r)=S[0\dots r-l)$. If $i\ge r$, no reusable comparison information reaches $i$, and extension starts from zero.

If $i\lt r$, position $i$ mirrors prefix position $k=i-l$. Initialize $Z[i]=\min(Z[k],r-i)$. When $Z[k]\lt r-i$, the mirrored match and its stopping mismatch lie inside the box, so no new comparison is needed. When $Z[k]\ge r-i$, equality is guaranteed only through $r-1$ and direct comparison resumes at the boundary. If $i+Z[i]\gt r$, update $l=i$ and $r=i+Z[i]$.

Linear Construction

Initialize $l=r=0$. At each $i$ from $1$ through $n-1$, copy the guaranteed part when $i\lt r$, extend with direct comparisons, and replace the active box when the new match reaches farther right.

The total work is linear. Every successful comparison made beyond the current box increases the global right endpoint $r$, which can advance at most $n$ times. Each outer position causes at most one failed comparison that stops extension. Copying inside the box adds only constant work, so construction is $O(n)$.

def z_algorithm(text: str) -> list[int]:
    """Return the Z-array using a half-open active box [left, right)."""
    n = len(text)
    z = [0] * n
    left = right = 0

    for i in range(1, n):
        if i < right:
            z[i] = min(right - i, z[i - left])

        while i + z[i] < n and text[z[i]] == text[i + z[i]]:
            z[i] += 1

        if i + z[i] > right:
            left, right = i, i + z[i]

    return z


def find_occurrences(text: str, pattern: str) -> list[int]:
    """Return overlapping starts; empty pattern occurs at every boundary."""
    if pattern == "":
        return list(range(len(text) + 1))

    used = set(text) | set(pattern)
    separator_code = 0
    while chr(separator_code) in used:
        separator_code += 1
    separator = chr(separator_code)

    combined = pattern + separator + text
    z = z_algorithm(combined)
    offset = len(pattern) + 1
    return [
        i - offset
        for i in range(offset, len(combined))
        if z[i] >= len(pattern)
    ]


if __name__ == "__main__":
    assert z_algorithm("") == []
    assert z_algorithm("a") == [0]
    assert z_algorithm("aaaaa") == [0, 4, 3, 2, 1]
    assert z_algorithm("aabcaabxaaaz") == [
        0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0
    ]
    assert find_occurrences("banana", "ana") == [1, 3]
    assert find_occurrences("aaaaa", "aa") == [0, 1, 2, 3]
    assert find_occurrences("abc", "") == [0, 1, 2, 3]
    assert find_occurrences("a#ba#b", "a#b") == [0, 3]
    print(z_algorithm("aabcaabxaaaz"))

Applications

For exact matching, compute the Z-array of pattern + separator + text, using a separator outside both alphabets. If $m$ is the pattern length, every text-region value at least $m$ marks an occurrence, including overlaps.

A suffix beginning at $i$ is a border exactly when $i+Z[i]=n$. An integer $p$ is a period when $Z[p]\ge n-p$; if $p$ also divides $n$, the string is an exact power of its length-$p$ prefix.

For prefix length $k$, every position with $Z[i]\ge k$ starts an occurrence, and position zero contributes one more. Counts for all prefix lengths follow from a frequency table of exact Z-values and suffix sums from larger values to smaller ones.