The Z-Function — Linear-Time Computation with the [l, r] Z-Box

z[i] = length of the longest substring starting at i that matches a prefix of s. Watch the box reuse make the whole array O(n).

step 0

String, current i, the [l, r) Z-box, and z values

i = -
l = 0
r = 0 (exclusive)
mirror i−l = -
z[i] = -
prefix being compared Z-box [l, r) current i matched mismatch
Press Step to begin. We process i = 1, 2, …, n−1. Inside the box we copy z[i−l] clamped to the edge; otherwise we extend by explicit comparison. The right edge r only ever moves forward → O(n).

The algorithm (current line highlighted)

Self-contained visualization. r is stored exclusive (one past the last matching index), so the copy clamp is z[i] = min(r - i, z[i - l]). The Z-box s[l..r-1] always equals the prefix s[0..r-l-1]; that invariant is why copying z[i−l] is valid. See junior.md and professional.md for the correctness proof and the amortized r-pointer argument that makes this linear.