Z-algorithm — Z-array construction, O(n+m): Visual walkthrough

Everything below works on one running string. Let us fix it now so every figure speaks the same language.

Step 1 — What question does $Z [i]$ ask?

WHAT. Pick any starting position $i$ . Slide a copy of the beginning of the string so that its first letter sits over position $i$ . Now walk right, comparing letter-by-letter, and count how many letters match before the first disagreement. That count is $Z [i]$ .

$Z [i] = how many letters we counted length of the longest run where start of string s [0], s [1], \dots = starting at i s [i], s [i + 1], \dots$

$s [0], s [1], \dots$ — the prefix, read from the front.
$s [i], s [i + 1], \dots$ — the substring starting at $i$ , read from where we planted our copy.
"longest run" — we stop at the first mismatch (or at the end of the string).

WHY. This one number secretly powers pattern matching (glue pattern in front of text; a $Z$ -value equal to the pattern's length = a match). But first we must be able to read it.

PICTURE. The overlaid ruler below shows $Z [3] = 3$ : three green ticks, then the string ends.

Figure — Z-algorithm — Z-array construction, O(n+m)

Recall Check your reading

Why is $Z [3] = 3$ and not $4$ ? ::: After matching aab (3 letters) we reach position $3 + 3 = 6$ , which is off the end of the string — there is no letter to compare, so we stop at $3$ .

Step 2 — The naive method, and why it hurts

WHAT. The obvious plan: for every starting position $i$ , replant the ruler and count from scratch. No memory, no cleverness.

WHY it is slow. Consider the cruel input $s = aaaaaa$ . At position $1$ you match $5$ letters, at position $2$ you match $4$ , and so on. You re-scan almost the whole tail every single time:

$total comparisons \approx (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = O (n^{2})$

$n$ — the length of the string.
The sum $(n - 1) + (n - 2) + \dots$ — the work at each position, added up.
$O (n^{2})$ — grows like the square of the length: double the string, quadruple the work.

This is the same quadratic wall the KMP failure function and String Hashing were invented to break. We want $O (n)$ : work that grows only proportionally to the string.

PICTURE. The staircase of re-scanned regions — notice how much red overlap is wasted re-work.

Step 3 — The one idea: the string photocopies itself

WHAT. Suppose at some earlier position we discovered a long match — say starting at position $l$ we matched the prefix for a good while, ending at position $r$ . Then the whole stretch of letters $s [l .. r]$ is letter-for-letter identical to the prefix $s [0.. r - l]$ . We call $[l, r]$ a Z-box: a window we already proved equals the front of the string.

$the window we found s [l .. r] = the prefix, same length s [0.. r - l]$

$l$ — left edge of the window (where the matched copy of the prefix begins).
$r$ — right edge (last position we verified).
$r - l$ — the window's length minus one, so the prefix piece $s [0.. r - l]$ has the same length as $s [l .. r]$ .

WHY this is gold. Inside this window the string is a photocopy of its own beginning. So a letter at position $i$ inside the window is guaranteed equal to the letter at its mirror position near the front. We can steal answers we already computed there — for free, with zero new comparisons.

PICTURE. The window $[l, r]$ (mint) laid directly beneath the identical prefix (lavender); dashed lines connect each position to its mirror.

Step 4 — The mirror position, defined exactly

WHAT. Take a position $i$ sitting inside the box ( $l \leq i \leq r$ ). Its mirror in the prefix is:

$i^{'} = i - l$

$i$ — where we currently stand, inside the window.
$l$ — the window's left edge.
$i - l$ — how far $i$ is from the left edge; that same distance from the front of the string lands on the mirror $i^{'}$ .

WHY. Because the window is a photocopy of the prefix, the letter at $i$ equals the letter at $i^{'}$ , and more: whatever match length we found earlier at $i^{'}$ (the value $Z [i^{'}]$ ) should copy over to $i$ — as long as that match stays inside the window.

PICTURE. Position $i$ inside the mint box; arrow folds back to $i^{'} = i - l$ in the lavender prefix. The little match-run at $i^{'}$ is shown ready to be copied to $i$ .

Step 5 — Case B1: the mirror's match fits inside the box

WHAT. We are inside the box and we compare two lengths: how far the mirror matched, $Z [i^{'}]$ , versus how much room is left to the box edge, $r - i + 1$ .

$room to edge = r - i + 1$

$r$ — right edge of the window.
$i$ — current position.
$r - i + 1$ — count of positions from $i$ up to and including $r$ (that "+1" includes $i$ itself).

If $Z [i^{'}] < r - i + 1$ , the mirror's entire match — including the mismatch that ended it — lives inside the window. Since the window is an exact copy, that same match and that same terminating mismatch repeat at $i$ :

$Z [i] = Z [i^{'}] (no comparisons at all)$

WHY no comparison. The letter that broke the mirror's match is inside the window, so it is a known, copied letter. It is guaranteed to break the match at $i$ in exactly the same spot. Re-checking would be redundant.

PICTURE. The mirror's short match (green) with its red mismatch, both safely inside the box, copied verbatim over to $i$ .

Step 6 — Case B2: the mirror's match runs off the box edge

WHAT. Now $Z [i^{'}] \geq r - i + 1$ : the mirror matched at least all the way to the box boundary. Up to the edge $r$ we can trust the copy — but beyond $r$ we have no photocopy, so we must compare by hand:

$Z [i] = trusted, from the box (r - i + 1) + must verify past r (extra matches found by comparing)$

$(r - i + 1)$ — the portion we get for free, up to the edge.
the extra term — new letters we actually compare, starting at position $r + 1$ , walking right until a mismatch.

Whatever we discover past $r$ extends the box: we set $l = i$ and $r = i + Z [i] - 1$ , because we now know a longer prefix-match reaching further right.

WHY the cap matters. Blindly copying $Z [i^{'}]$ here would claim matches beyond $r$ that were never checked — a lie. We trust only up to the edge, then verify.

PICTURE. The mirror's match overshoots the box edge; green up to $r$ , then a "?" zone beyond $r$ where fresh comparisons begin (and push $r$ forward).

Step 7 — The degenerate cases (never leave a gap)

WHAT. Three boundary situations the picture must cover:

$i > r$ — outside every box. No photocopy exists. Start fresh: $Z [i] = 0$ , then compare from position $0$ . If anything matches, open a new box.
$Z [i^{'}] = 0$ inside the box. The mirror never matched; $min (r - i + 1, 0) = 0$ , and the first comparison at $i$ likely fails too. Nothing gained, nothing broken.
Match reaches the very end of the string. The while stops because $i + Z [i] = n$ (no letter to compare), not because of a mismatch. Position $2$ of aab at the string's tail is exactly this.

WHY it matters. The amortized $O (n)$ argument relies on $r$ only ever increasing. That is why the parent note's third mistake — updating the box when the new match does not reach past $r$ — is forbidden: it would let $r$ shrink and destroy linearity.

PICTURE. Three mini-panels: (1) fresh start past $r$ , (2) zero mirror, (3) run-off-the-end. Each shows the box edge $r$ never moving backward.

Step 8 — Full trace on $s = aabaab$

WHAT. Watch $[l, r]$ crawl rightward as we fill $Z$ left to right.

$i$	case	$min (r - i + 1, Z [i^{'}])$	after `while`	box $[l, r]$
1	$i > r$	—	$Z [1] = 1$	$[1, 1]$
2	$i > r$	—	$Z [2] = 0$	unchanged
3	$i > r$	—	$Z [3] = 3$	$[3, 5]$
4	$i \leq r$ , $i^{'} = 1$	$min (2, 1) = 1$	$Z [4] = 1$ (B1)	unchanged
5	$i \leq r$ , $i^{'} = 2$	$min (1, 0) = 0$	$Z [5] = 0$	unchanged

Result: $Z = [-, 1, 0, 3, 1, 0]$ .

WHY it's linear here. Real character comparisons happened only while pushing $r$ from $0$ up to $5$ . Positions $4$ and $5$ paid nothing — they copied. The box swept forward once; it never retreated.

PICTURE. The moving box across all six positions, green "copied" positions distinguished from red "compared" ones.

The one-picture summary

Everything on this page collapses into a single diagram: the prefix, the rightmost box, the mirror fold, and the two cases branching at the box edge.

Recall Feynman: retell the whole walkthrough

Think of the string's first few letters as a stamp. You press that stamp along the string and count how many letters line up before one goes wrong — that count is $Z [i]$ (Step 1). Doing this from scratch everywhere is exhausting on boring inputs like aaaa (Step 2). But every long match you find is really a photocopy of the string's opening (Step 3), and any spot inside that photocopy has a twin near the front — its mirror (Step 4). If the twin's match sits fully inside the photocopy, just copy the twin's answer, no work (Step 5, B1). If the twin's match spills over the photocopy's right edge, trust it up to the edge and then compare the rest by hand, which stretches the photocopy further right (Step 6, B2). When you're past the photocopy entirely, or the twin found nothing, or you hit the string's end — you handle those plainly, and crucially the right edge $r$ only ever moves forward (Step 7). Trace it on aabaab and you'll see the box crawl right exactly once, doing real comparisons only while growing (Step 8). Forward-only motion is the whole reason the total work is linear.