Z Algorithm Explained: Linear-Time Pattern Matching With a Z-Box

Finding a pattern in a text by trying every starting position is quadratic in the worst case: search for aaab in a long run of a and every attempt gets almost to the end before failing. KMP is the famous fix, and its failure table is famously hard to explain on a whiteboard. The Z algorithm gets the same linear bound with one array whose meaning fits in a sentence, and one idea, the z-box, that is easy to draw.

The problem it solves

For a string s, the Z array stores, at each position i, the length of the longest substring starting at i that matches a prefix of s. For aabxaab:

• z[1] = 1: from position 1, a matches the first character, then b does not match a.
• z[4] = 3: from position 4, aab matches the first three characters, then the string ends.
• z[0] is left as 0 by convention; the whole string trivially matches itself.

Pattern matching falls out directly. Build pattern + separator + text, where the separator appears in neither string, and compute its Z array. Every position in the text part where z[i] equals the pattern's length is an occurrence. The separator guarantees no match can run longer than the pattern.

Computed naively, each z[i] compares from scratch, and on aaaa… that is about n²/2 comparisons. The Z algorithm computes the whole array in O(n).

The intuition

Keep the z-box: the interval [lo, hi) of the match found so far that reaches furthest to the right. By definition, s[lo:hi] equals s[0:hi-lo], the start of the string.

Now take a position i inside the box. Because the box is a copy of the prefix, the characters from i to hi are identical to the characters from i - lo onwards near the front, its mirror. The algorithm already knows z[i - lo]. So:

• If the mirror's match ends before the box does, z[i] equals it exactly. No comparison needed.
• If it reaches the edge of the box, then z[i] is at least hi - i, and only characters past hi still need comparing, because nothing beyond the box has been proven.

That is the whole algorithm: z[i] = min(hi - i, z[i - lo]), then extend by direct comparison, then move the box if the new match reaches further right.

Why linear? Every comparison either fails, which ends the loop for that i and happens at most once per position, or succeeds past hi, which pushes the box's right edge forward. The right edge only moves right and stops at n. So there are at most n successful and n failed comparisons: fewer than 2n in total.

Watch it run

The animation computes the Z array of aabxaab. z[i] is how far position i matches the start of the string, and comparing each one from scratch would be quadratic. At position 1 there is no box yet, so it compares from the start and gets 1, and that match becomes the new box. At 2, b does not match the first character, so z[2] = 0 after a single comparison; the same happens to x at 3. Position 4 is outside any box again: compare from the start, get 3, and that match becomes the new box. Position 5 sits inside the box, so its mirror at 1 already answers 1 of it, and only the rest is compared. Position 6 sits inside too; its mirror at 2 answers 0. The last frame states the invariant: every comparison either confirmed a character or pushed the box right, and the box never slid back, so the whole scan is O(n).

The code

The Z array itself, with the box as two indices:

def z_array(s):
    z = [0] * len(s)
    lo = hi = 0                                  # the z-box is s[lo:hi]
    for i in range(1, len(s)):
        if i < hi:
            z[i] = min(hi - i, z[i - lo])        # copy from the mirror, capped at the box
        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
            z[i] += 1                            # compare only past what is proven
        if i + z[i] > hi:
            lo, hi = i, i + z[i]                 # a box reaching further right
    return z

print(z_array("aabxaab"))     # [0, 1, 0, 0, 3, 1, 0]
print(z_array("aaaaa"))       # [0, 4, 3, 2, 1]
print(z_array("abacaba"))     # [0, 0, 1, 0, 3, 0, 1]

Pattern search is one call on the concatenation. The separator is a character that cannot occur in either input:

def find_all(pattern, text, sep="\x00"):
    s = pattern + sep + text                     # sep occurs in neither string
    z = z_array(s)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(s)) if z[i] >= m]

print(find_all("aba", "abababa"))   # [0, 2, 4]
print(find_all("xyz", "abababa"))   # []

Overlapping matches come out naturally, which a replace-based approach would miss. To see the linear bound instead of trusting it, both versions below count character comparisons on 2,000 copies of a, the worst case for the naive scan:

def z_counted(s):
    """Same algorithm, counting character comparisons."""
    z, lo, hi, comparisons = [0] * len(s), 0, 0, 0
    for i in range(1, len(s)):
        if i < hi:
            z[i] = min(hi - i, z[i - lo])
        while i + z[i] < len(s):
            comparisons += 1
            if s[z[i]] != s[i + z[i]]:
                break
            z[i] += 1
        if i + z[i] > hi:
            lo, hi = i, i + z[i]
    return z, comparisons

def z_naive(s):
    z, comparisons = [0] * len(s), 0
    for i in range(1, len(s)):
        while i + z[i] < len(s):
            comparisons += 1
            if s[z[i]] != s[i + z[i]]:
                break
            z[i] += 1
    return z, comparisons

s = "a" * 2000
print(z_counted(s)[1], z_naive(s)[1])      # 1999 1999000

Checked on 2,000 seeded random strings over ab, the alphabet that produces the most repeats: the fast Z array must match the naive one, the comparison count must stay below 2n, and find_all must match a slice-by-slice brute-force search:

import random

random.seed(27)
ok, worst = True, 0.0
for _ in range(2_000):
    s = "".join(random.choice("ab") for _ in range(random.randint(1, 60)))
    fast, comparisons = z_counted(s)
    ok &= fast == z_array(s) == z_naive(s)[0]
    worst = max(worst, comparisons / len(s))
    p = "".join(random.choice("ab") for _ in range(random.randint(1, 4)))
    ok &= find_all(p, s) == [i for i in range(len(s) - len(p) + 1) if s[i:i + len(p)] == p]
print(ok, worst < 2)                         # True True

The complexity

• Time: O(n) for the Z array, fewer than 2n character comparisons. Pattern search on a text of length n and a pattern of length m is O(n + m), the same bound the Big-O cheat sheet lists for the other linear matchers.
• Space: O(n + m) for the concatenated string and its Z array. KMP needs only O(m) for its table, which is the one place it wins.

Where it goes wrong

• Forgetting the cap. Copying z[i - lo] without min(hi - i, …) claims matches beyond the box that were never verified.
• A separator that can occur in the input. Then a match can run through it, past the pattern's end. Use a character outside the alphabet.
• Updating the box on every position. Move it only when the new match reaches further right; otherwise the right edge could move backwards and the linear argument breaks.

When it shows up in interviews

Directly, as "find all occurrences of a pattern in linear time", where it is the easiest linear algorithm to write from memory. Indirectly, in string problems about prefixes: the shortest period of a string, counting how often each prefix occurs, or the longest prefix that is also a suffix. It sits beside KMP's failure table, which answers the same questions with a border array, and Rabin-Karp, which trades the guarantee for hashing.

How to say it in an interview

"z of i is the length of the longest match between the string starting at i and the string's own prefix. I keep the rightmost match window, the z-box. For a position inside it, the part up to the box edge is a copy of the prefix, so I start from the mirror's value capped at the box edge and only compare past it. Every successful comparison pushes the box right and every failure ends a position, so it is fewer than 2n comparisons. For pattern search I run it on pattern, separator, text and report positions where z equals the pattern length."