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.
The picture: the prefix, seen again
The walk on aabaabcaabaa. Cells highlighted in the prefix (0–4) reappear at indices 7–11. The row of numbers under the characters is the Z-array. Note Z[10] = 2: the earlier answer Z[3] = 3 would run past the end of the box, so it is capped at r − i.
Worked example, step by step
Take aabaabcaabaa and build its Z-array left to right, keeping the box [l, r) of the match that reaches furthest right. The last column counts character comparisons made at that index, so you can see where the saving comes from.
i
Suffix
How Z[i] starts
Start
Z[i]
Box [l, r)
Compares
1
abaabcaabaa
outside box: compare fresh
0
1
[1, 2)
2
2
baabcaabaa
outside box: compare fresh
0
0
[1, 2)
1
3
aabcaabaa
outside box: compare fresh
0
3
[3, 6)
4
4
abcaabaa
inside box: mirror z[1]=1, cap r-i=2
1
1
[3, 6)
1
5
bcaabaa
inside box: mirror z[2]=0, cap r-i=1
0
0
[3, 6)
1
6
caabaa
outside box: compare fresh
0
0
[3, 6)
1
7
aabaa
outside box: compare fresh
0
5
[7, 12)
5
8
abaa
inside box: mirror z[1]=1, cap r-i=4
1
1
[7, 12)
1
9
baa
inside box: mirror z[2]=0, cap r-i=3
0
0
[7, 12)
1
10
aa
inside box: mirror z[3]=3, cap r-i=2
2
2
[7, 12)
0
11
a
inside box: mirror z[4]=1, cap r-i=1
1
1
[7, 12)
0
The whole array is [12, 1, 0, 3, 1, 0, 0, 5, 1, 0, 2, 1], found with 17 character comparisons. Computing each Z-value from scratch takes 22 on the same string. Six of the eleven steps (highlighted) began inside the box. At i = 10 and i = 11 the mirrored value was already the answer and cost no comparison at all. At i = 10 the mirror said 3 but the box had only 2 characters left, so the value was capped at 2. That cap, min(Z[i − l], r − i), is the line people drop. Past the box the algorithm knows nothing, so it compares fresh, and every successful comparison pushes r right, which can only happen n times in total.
Complexity and trade-offs
Case
Time
Space
Why
Z-algorithm
O(n)
O(n)
r only moves right, so successful comparisons total at most n. Measured on 'a'×999 + 'b': 1997 comparisons.
Naive Z-array
O(n²)
O(n)
Restarts the comparison at every index. Same 1,000-character string: 499500 comparisons.
Pattern search, Z on P#T
O(n + m)
O(n + m)
Linear in pattern plus text. On a 499-a pattern ending in b against 1,000 a’s: 2499 comparisons, against 250500 for naive search.
KMP failure function
O(n + m)
O(m)
Carries the same information as the Z-array, and the search needs memory only for the pattern, not for pattern plus text.
Rabin–Karp
O(n + m) expected, O(nm) worst
O(1)
Hash comparisons are cheap but can collide; matches must be verified, and adversarial inputs can force the worst case.
Z and KMP are interchangeable in power; the Z-array is usually easier to reason about because Z[i] has a plain meaning (“how far does the suffix at i match the prefix?”) that you can check by hand. The price is memory: searching with Z builds an array over pattern plus text, while KMP keeps only a table the length of the pattern. For a text that streams past once, KMP’s smaller state is the better fit; for offline analysis of a single string, Z is often the clearer tool.
Common mistakes
Dropping the cap
Writing z[i] = z[i − l] instead of min(z[i − l], r − i) trusts the mirror beyond the box. On "aaa" it returns [3, 2, 2] instead of [3, 2, 1]: the last index claims to match 2 characters with only 1 left.
Forgetting to extend
Inside the box, the mirror value is only a lower bound when it reaches the box edge. Stopping there without comparing characters past r misses longer matches. Extend whenever the mirror value equals r − i.
Searching without a separator
Concatenating P + T directly lets matches run across the join. For P = "aa", T = "aaaa" only index [2] has Z == |P|, while the pattern really occurs at [0, 1, 2]. Insert a character in neither string, and test Z[i] == |P|.
Picking a separator that occurs in the text
Using "a" as the separator for P = "aa", T = "aaa" reports [1] instead of [0, 1]. The separator must be outside the alphabet of both strings, or you must compare against |P| and clamp.
Resetting the box on every index
Setting l, r = i, i + z[i] unconditionally, instead of only when i + z[i] > r, keeps the answers correct but throws away the widest box. On 'ab'×20 + 'c' that costs 420 comparisons instead of 78, the quadratic behaviour coming back.
Where this shows up
Finding every occurrence of a pattern
The page’s search recipe: compute the Z-array of P#T and report indices with Z[i] == |P|. It returns every match, including overlapping ones, in one pass.
Smallest repeating unit
A string of length n is built from a repeated block of length p when p divides n and p + Z[p] == n. For abcabcabc the first such p is 3, so the string is three copies of abc.
Borders and prefix occurrences
A border is a prefix that is also a suffix: it is any index i with i + Z[i] == n. And the number of places a prefix of length k occurs is the count of indices with Z[i] ≥ k: in abababab, the prefix ab occurs at 4 positions.
Contest and interview string problems
Many “longest prefix that also appears elsewhere” and “how similar is each suffix to the start” questions are one Z-array away, and the code is short enough to write from memory.
SOLVE IT YOURSELF
Solve it: build the Z-array
The Z-array answers "how far does the string match itself starting here?" for every position — in one linear pass, by reusing what earlier positions already proved. Write it in Python or TypeScript, running for real in your browser.
YOUR TASK
Implement z_array(s): return a list where z[i] is the length of the longest substring starting at i that is also a prefix of s. By convention z[0] is the whole length. So "aabxaab" gives [7, 1, 0, 0, 3, 1, 0].
HINTS — 5 IDEAS
Track a window[l, r) — the rightmost match-with-the-prefix found so far.
If i is inside that window, the answer at mirror position i - l already tells you a head start: z[i] = min(r - i, z[i - l]).
The min is essential — you may only trust the mirror up to the window edge; past it, nothing has been compared yet.
Then extend by brute force from wherever the head start left off.
If you pushed past r, slide the window: l, r = i, i + z[i]. Each character is compared at most twice, so the whole thing is O(n).
CPython · WebAssembly✓ Solved
1
1
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.