Don't memorize the Z-algorithm — watch the Z-box slide. The Z-array records, at every position, how far the string still matches its own prefix. The magic is a cached window [l, r] — the match that reaches furthest right. When your index sits inside it you mirror an earlier answer for free; only when the mirror runs into the edge do you compare fresh characters and push the window along. That is why the whole thing is O(n).
Z[i] = prefix match at i · reuse inside [l, r] · extend past r · linear time
Z-ARRAY
Z[i] = length of the longest substring starting at i that is also a prefix of the string.
Z-BOX [l, r]
The prefix-match that currently reaches furthest right: s[l..r] equals a prefix.
MIRROR
Inside the box, reuse Z[i − l] from the matching earlier position — no comparisons.
EXTEND
If the mirror hits the box edge, compare past r and slide the window right.
z.sim — Z-array of "aabaabaaaab"
Ready
Each Z[i] is how far the suffix at i re-matches the prefix. The amber [l, r] box caches the furthest-right match. Press Step: inside the box we mirror; outside, or past its edge, we compare fresh.
i ≤ r: Z[i] = min(Z[i−l], r−i+1); then extend if needed
—
Index i
—
Z[i]
The window pays for itself
A naive Z-array compares every position against the prefix from scratch — O(n²). The Z-algorithm keeps one extra piece of state: the interval [l, r] of the match that currently extends furthest to the right, where s[l..r] is known to equal a prefix. Now take any index i inside that window. Because s[l..r] mirrors the prefix, the characters at i look exactly like the characters at i − l — which you already solved. So Z[i] starts as Z[i − l], capped by how much of the window is left, r − i + 1. If the mirrored value fits inside the window, you are done with zero comparisons. Only when it reaches the edge do you compare characters beyond r, and every such comparison that succeeds moves r forward — which can happen at most n times total. Linear.
01
Define Z
Z[0] = n; for i > 0, Z[i] is the match length of the suffix at i against the prefix.
02
Keep the box
Maintain [l, r], the prefix-match reaching furthest right seen so far.
03
Mirror inside
If i ≤ r: set Z[i] = min(Z[i − l], r − i + 1) — reuse the earlier answer for free.
04
Extend when capped
Compare characters past r; on success push r right and reset l = i.
Time
O(n + m)
Space
O(n)
Amortized
r only grows
Search
P # T
To search for a pattern P inside a text T, build P + # + T with a separator that appears in neither, and compute its Z-array in one pass. Every position where Z[i] = |P| is an occurrence of the pattern — all matches, in O(n + m), matching the Knuth–Morris–Pratt bound with code that many find simpler. The Z-array and the KMP prefix function carry the same information in different clothes; Rabin–Karp reaches the same goal through hashing. Different lenses, one linear-time idea.
Check yourself
1 · What does Z[i] measure?
Z[i] is how far the suffix beginning at i re-matches the whole string's prefix — the core quantity the algorithm fills in.
2 · What is the point of the [l, r] Z-box?
Inside the box, s looks like the prefix, so Z[i] can start from the mirrored Z[i − l] — that reuse is what removes the O(n²) blow-up.
3 · Why is the whole computation O(n)?
Successful comparisons advance r (at most n times total); each index adds at most one failing comparison — amortized linear.
Questions
Z-array vs the KMP prefix function?
Both are linear-time, prefix-based string tools. The Z-array gives, per position, the match length with the prefix; the KMP failure function gives the longest proper prefix that is also a suffix. They carry equivalent information and can be converted into each other.
How do I search for a pattern with it?
Concatenate P + separator + T, compute the Z-array, and report every index where Z[i] = |P|. Each such position is a full occurrence of the pattern in the text, found in O(n + m).
Why a separator character?
The separator (a symbol in neither P nor T) stops a match from spilling across the boundary between pattern and text, so no Z-value can exceed |P|. That makes Z[i] = |P| an exact test for a full pattern match.
One window, and O(n²) becomes O(n).
Mirror the answers the Z-box already knows, compare fresh only when you must extend — the string tells you where it repeats itself in one pass.