Z-Algorithm

The Z-algorithm computes, for every position i in a string, how long the substring starting at i matches the prefix of the string. That single array unlocks fast pattern matching, period detection, and prefix-overlap queries — all in one linear pass.

For s = "aabaab" the z-array is [–, 1, 0, 3, 1, 0]. The 3 at index 3 says aab reappears starting there — which is exactly how you find a pattern inside text.

Intuition

A brute-force z[i] walks forward from i and from 0 in lockstep until the characters differ — that is O(n) per index, O(n²) overall. The Z-algorithm avoids redoing that work.

Whenever a comparison matches far to the right, it remembers that interval as the z-box [l, r]: everything from l to r is known to equal the prefix s[0 .. r-l]. So when a later index i falls inside the box, the answer at its mirror position i - l already describes the same characters. As long as that mirror match stays within the box, we copy it for free. Only when an index reaches past r, or a mirror match runs to the box edge, do we fall back to direct comparison — and that comparison only ever pushes r forward, never backward.

Walk through it

Step through the animation. The top row is s; the bottom row fills in with z-values. The l and r pointers mark the current z-box.

The first three indices all sit at or past r, so they compare directly: z[1] = 1 (and the box slides to [1, 1]), z[2] = 0 (box unchanged), then index 3 matches aab against the prefix aab for z[3] = 3, growing the box to [3, 5]. Now reuse kicks in. Index 4 is inside [3, 5]; its mirror i - l = 1 has z[1] = 1, which stays inside the box, so z[4] = 1 with zero comparisons. Index 5 mirrors z[2] = 0, so z[5] = 0, again free. That reuse is the whole point: each character is examined at most once.

The code, line by line

def z_array(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i > r:                 # outside the box
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            if i + z[i] - 1 > r:
                l, r = i, i + z[i] - 1
        else:                     # inside the box
            k = i - l
            if z[k] < r - i + 1:
                z[i] = z[k]        # safe reuse
    return z

• z[0] is left as 0 and the loop starts at 1, because z[0] would just be n (the string matches itself) and is never useful.
• Line 6 splits the two cases: if i is past r, there is no box to lean on, so we compare from scratch in the while.
• The while extends the match character by character; i + z[i] - 1 > r then checks whether this match reaches farther right than the current box, updating l, r if so.
• The else branch handles i inside the box. The mirror index k = i - l points at the equivalent prefix position.
• z[k] < r - i + 1 means the mirror match fits entirely inside the box, so z[i] = z[k] is exact and we copy it with no comparison. (When it does not fit, a fuller version compares forward from r; this lesson focuses on the safe-reuse case.)

Complexity

The while loop looks like it could make the scan quadratic, but every successful comparison advances r by one, and r only increases across the whole run — so all comparisons together are bounded by n. Inside-the-box indices do no comparisons at all. That gives a clean linear bound.

When to use / pitfalls

Practice