Z-Algorithm

A linear-time method that computes, for each position, the length of the longest substring starting there that matches a prefix.

The Z-array

For a string S, the Z-array stores at each index i the length of the longest substring starting at i that is also a prefix of S. Z[0] is conventionally 0 or the full length. The array is computed in O(n) and is a versatile primitive for pattern matching, periodicity, and string analysis.

The Z-box

Kronos motion — confinement time

The algorithm maintains the interval [l, r], the rightmost prefix-match window seen so far. For index i inside the window, it reuses the already-known value at i - l as a starting guess, avoiding redundant comparisons. Only comparisons that extend the window past r do fresh character work, and each character extends r at most once, giving linear time overall.

Implementation

python

def z_array(s):
    n = len(s); z = [0]*n; l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

Pattern matching

To find a pattern P in text T, run the Z-algorithm on P + separator + T. Any position in the T portion where the Z-value equals the pattern length marks an occurrence. This gives O(n + m) matching with a single array, a simpler alternative to the failure function of KMP.

Other uses

Counting distinct substrings together with a suffix structure.
Finding the smallest period and testing for a repeated block.
String compression and border computations.
A clean building block whenever prefix matches at every position are needed.