Z-Algorithm, in depth: the Z-box invariant, a linear-time proof, pattern search in O(m) memory, periods and the prefix function

What the Z-array is

Fix a string s of length n, indexed from zero. For each position i, Z[i] is the length of the longest string that is both a prefix of s and a prefix of the suffix s[i:]. In other words, start reading at 0 and at i simultaneously and count how many characters agree before the first mismatch or the end of the string.

For s = aabxaabxaa the array is [10, 1, 0, 0, 6, 1, 0, 0, 2, 1]. Position 4 scores 6 because aabxaa starts there and also starts the string; position 8 scores 2 because aa is all that remains. Z[0] is degenerate: the whole string trivially matches itself. Some libraries store n, others store 0. Pick one, write it down, and never let a caller rely on it, because it is the single most common source of off-by-one disagreements between implementations.

The naive way to fill the array compares from scratch at every i. On aaaa...a each comparison runs to the end of the string, so the cost is n + (n-1) + ... = O(n^2). The Z-algorithm removes the repeated work with one observation.

What the Z-array is

Fix a string s of length n, indexed from zero. For each position i, Z[i] is the length of the longest string that is both a prefix of s and a prefix of the suffix s[i:]. In other words, start reading at 0 and at i simultaneously and count how many characters agree before the first mismatch or the end of the string.

For s = aabxaabxaa the array is [10, 1, 0, 0, 6, 1, 0, 0, 2, 1]. Position 4 scores 6 because aabxaa starts there and also starts the string; position 8 scores 2 because aa is all that remains. Z[0] is degenerate: the whole string trivially matches itself. Some libraries store n, others store 0. Pick one, write it down, and never let a caller rely on it, because it is the single most common source of off-by-one disagreements between implementations.

The naive way to fill the array compares from scratch at every i. On aaaa...a each comparison runs to the end of the string, so the cost is n + (n-1) + ... = O(n^2). The Z-algorithm removes the repeated work with one observation.

The Z-box: reusing work you already did

Suppose that while processing earlier positions we found some l with Z[l] > 0. Then the window s[l:r], where r = l + Z[l], is an exact copy of s[0:r-l]. Call it the Z-box. Among all boxes found so far, keep the one whose right end r is furthest along.

Now take a new position i with l < i < r. Because s[l:r] equals s[0:r-l], the characters from i to r are identical to the characters from k = i - l to r - l. We already computed Z[k]. That tells us how far s[k:] agrees with the prefix, which means s[i:] agrees with the prefix for at least the same distance, as long as we stay inside the box. Two sub-cases follow:

• If Z[k] < r - i, the match at k ended strictly inside the mirrored region, at a character that also lies inside the box. The same mismatch happens at i, so Z[i] = Z[k] exactly and no comparison is needed.
• If Z[k] >= r - i, we only know that the first r - i characters agree; beyond r we have never looked. Start Z[i] at r - i and extend by direct comparison, then move the box to [i, i + Z[i]).

If i is at or beyond r, the box tells us nothing and we compare from scratch. The implementation folds the cases together: initialise Z[i] to min(r - i, Z[i - l]) when inside the box, then run the same extension loop in every case. In the first sub-case the loop fails on its first comparison, which costs O(1).

Why it runs in linear time

Count comparisons in two kinds. A failed comparison ends the extension loop, so there is at most one per position: n in total. A successful comparison at position i examines character i + Z[i], which is at or beyond r, and afterwards the box is moved so that r is larger than before. Since r only moves right and never exceeds n, there are at most n successful comparisons in the whole run. Everything else per iteration is constant work, so the algorithm runs in O(n) time with O(n) memory for the array.

This is the same amortised argument used for KMP, but it is easier to verify in code review: look for the single variable r, confirm it is only ever assigned a larger value, and confirm every character comparison sits on its frontier.

Worked example: a full trace

Trace s = aabxaabxaa with the box starting empty at l = r = 0.

Position 8 is the instructive one. The mirror value Z[4] = 6 is far larger than what is left of the box, so the clamp to r - i = 2 is what keeps the answer correct. Forget the clamp and you report a match of length 6 that runs off the end of the string. Positions 5 to 7 show the other sub-case: the mirrored value is small, and a single failed comparison confirms it. In total the run made 13 character comparisons for 10 characters against 17 for the naive method, and on aaaaaaaaaa it makes 45 successful ones against the Z-algorithm's 9.

Reference implementation

The reference implementation below is the one used in the rest of the article. It is iterative, allocates one list, and works on any indexable sequence, so it handles Python strings, bytes, lists of token IDs or arrays of hashes equally well.

def z_array(s):
    """Z[i] = length of the longest common prefix of s and s[i:]. Z[0] = len(s) by convention."""
    n = len(s)
    z = [0] * n
    if n == 0:
        return z
    z[0] = n
    l, r = 0, 0                       # current Z-box is s[l:r], and s[l:r] == s[0:r-l]
    for i in range(1, n):
        if i < r:                     # inside the box: reuse the mirrored value, clamped to the box
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                 # every successful comparison here pushes r forward
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

For testing, the brute-force definition is three lines: for each i, count while s[k] == s[i + k]. Compare both on a few thousand random strings over a two-letter alphabet; small alphabets produce long matches and exercise the clamp far more often than English text does. Every snippet here passed that test.

Pattern search without a separator

The textbook search builds pattern + '$' + text with a separator that occurs in neither, computes Z on the whole thing, and reports every text position whose value equals len(pattern). The separator caps every value at m, so no match can spill across the boundary. It works, but it allocates a string and an array of size n + m + 1 and it needs a character guaranteed absent from the input, which is a real problem for bytes or token IDs.

A cleaner version computes Z only for the pattern and then walks the text with the same box logic. The box now lives in the text, mirroring a prefix of the pattern, and the clamp reuses the pattern's own Z-values. Memory is O(m), the text can be streamed in order, and no sentinel is needed.

def find_all(pattern, text):
    """All start offsets of pattern in text. Extra memory O(len(pattern)); no separator needed."""
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    zp = z_array(pattern)
    hits = []
    l, r = 0, 0                       # box in text: text[l:r] == pattern[0:r-l]
    for i in range(len(text)):
        k = min(r - i, zp[i - l]) if i < r else 0
        while k < m and i + k < len(text) and pattern[k] == text[i + k]:
            k += 1
        if i + k > r:
            l, r = i, i + k
        if k == m:
            hits.append(i)
    return hits

For find_all('aab', 'baabaab') this returns [1, 4]. The time bound is unchanged at O(n + m): r still only moves right, now across the text. Because the inner loop reads at most m characters ahead of i, a streaming caller needs a look-ahead buffer of m characters, not the whole document.

Periods, borders and other uses

Once the array exists, several problems become short loops.

• Shortest period. The smallest p with p + Z[p] = n is the shortest period of s: the suffix starting at p equals a prefix, so s repeats with step p. For abababab it returns 2. If p divides n the string is an exact power, which is how compressors and log deduplicators detect repeated records.
• Borders. Every i with i + Z[i] = n marks a prefix of length n - i that is also a suffix. Listing them gives all borders, the quantity KMP's failure function is built from.
• Prefix function. The conversion below produces KMP's pi array in linear time, so if you have one well-tested routine you can derive the other rather than maintaining two.
• Matching with one mismatch. Run Z on pattern + text forward and on their reverses. At an alignment, if the forward match length plus the backward match length covers m - 1 characters, the pattern occurs with at most one substitution. This is a standard trick in bioinformatics and fuzzy log search.

def smallest_period(s):
    """Smallest p such that s[i] == s[i + p] for all valid i."""
    z, n = z_array(s), len(s)
    for p in range(1, n):
        if p + z[p] == n:             # the suffix at p is also a prefix
            return p
    return n

def z_to_prefix_function(z):
    """KMP's pi array from the Z-array, in O(n)."""
    n = len(z)
    pi = [0] * n
    for i in range(1, n):
        if z[i]:
            end = i + z[i] - 1
            pi[end] = max(pi[end], z[i])
    for i in range(n - 2, 0, -1):
        pi[i] = max(pi[i], pi[i + 1] - 1)
    return pi

Z-algorithm against the alternatives

In production code, a library's built-in substring search, which is usually a tuned two-way or Boyer-Moore-Horspool hybrid, beats a hand-written Z search on plain text. Reach for Z when you need the array itself, when the alphabet is not characters, or when you need a worst-case linear guarantee you can read in one screen.

Failure modes

• Missing clamp. Writing z[i] = z[i - l] without the min against r - i reads past what the box guarantees. It passes most English tests and fails on periodic inputs, which is exactly the case in the trace above.
• Updating the box unconditionally. Setting l = i on every iteration loses a box that extends further right. The answer stays correct but the running time degrades to quadratic on inputs like aaaa
• Separator collisions. Using '$' or '#' as a separator on user input, file paths or byte arrays lets matches cross the boundary. Use the pattern-only search above, or a sentinel object outside the alphabet such as None in a list.
• Z[0] confusion. Code that loops from 0 and treats Z[0] = n as a match reports the pattern at a phantom position. Start every consumer loop at 1, or at m + 1 in the concatenated form.
• Unicode units. In languages where strings are UTF-16 or UTF-8 code units, a match can begin in the middle of a code point. Normalise and compare at the level you mean, code points or grapheme clusters, before computing positions you will show to users.

What to do next

Related reading on this site: KMP and the failure function for the online alternative, the string matching survey for choosing between algorithms, Manacher's algorithm, which uses the same box-and-mirror idea for palindromes, and tries for many-pattern prefix problems.

1. Type out z_array from memory, then test it against the brute-force definition on 5,000 random strings over the alphabet {a, b}.
2. Hand-trace aaaaab and confirm the number of successful comparisons never exceeds n.
3. Replace one substring search in a tool you own that runs on token IDs or bytes with find_all, and measure it against the built-in.
4. Use smallest_period to detect repeated records in a log or a sequence of request IDs.
5. Derive the prefix function with z_to_prefix_function and check it matches your KMP implementation on random inputs.
6. Try the forward-plus-reverse trick to find matches with one mismatch, and write a test that includes a mismatch at the first and last character.