What the Z-array measures
By now you have met the naive scan that re-checks the pattern from scratch at every alignment, and you have seen how Knuth-Morris-Pratt avoids that waste by precomputing how the pattern overlaps itself. The Z-algorithm chases the same prize — linear-time exact matching — but it asks a single, beautifully concrete question about one string and answers it for every position at once. That single answer turns out to be enough to solve matching, and many other string puzzles, almost for free.
Fix a string `S` of length `n`. The Z-array stores, for each index `i` from 1 to n-1, the value `Z[i]` = the length of the longest stretch starting at position `i` that exactly matches a stretch starting at the very beginning of `S`. In words: how far can you read `S` from position `i` and from position 0 in lockstep before the two characters disagree (or you run off the end)? Position 0 is special and we usually leave `Z[0]` undefined, since the whole string trivially matches itself there.
S = a a b a a b a a a idx 0 1 2 3 4 5 6 7 8 Z - 1 0 5 1 0 2 2 1 Z[3]=5: "aabaa" at pos 3 matches prefix "aabaa", then a vs b breaks Z[6]=2: "aa" at pos 6 matches prefix "aa", then 'a' vs 'b' breaks
From Z-array to pattern matching
Why would a tool about one string help us match a pattern `P` against a text `T`? Here is the trick that makes it click. Build a new string `Glue = P + '#' + T`, where `#` is a separator character that appears in neither `P` nor `T`. Now run the Z-algorithm on `Glue`. Because the prefix of `Glue` is exactly `P`, any position `i` inside the `T` part with `Z[i]` equal to the length of `P` is a place where `P` reappears in full — that is a match. The separator guarantees no spurious overlap can stretch a Z-value past the end of `P`.
Translate the position back: a match found at `Glue` index `i` sits at index `i - (len(P) + 1)` in the original text `T`. So one pass of the Z-algorithm over a string of length `len(P) + 1 + len(T)` reports all occurrences. If `m = len(P)` and `n = len(T)`, this runs in O(m + n) time — the same headline cost as KMP, reached by a different and arguably simpler road.
The Z-box: reusing what we already matched
Computed naively, each `Z[i]` could cost up to `n` comparisons, dragging the whole thing back to O(n^2) in the worst case — exactly the trap the naive matcher fell into. The Z-algorithm escapes by carrying along a single window, the Z-box, recorded as an interval `[l, r]`. This box is the rightmost-reaching match-with-the-prefix we have discovered so far: the substring `S[l..r]` is known to equal `S[0..r-l]`, a prefix of `S`. The whole speed-up rides on one observation: inside that box, we have already compared those characters against the prefix, so we can copy old answers instead of re-reading.
Concretely, suppose we are about to compute `Z[i]` and `i` lies inside the current box, so `i <= r`. Because `S[l..r]` mirrors a prefix, the character at `i` corresponds to the character at the mirror position `k = i - l` near the front of `S`. We already know `Z[k]`. If `Z[k]` is small enough to fit entirely inside the box (it does not reach the boundary `r`), then `Z[i]` simply equals `Z[k]` — no character comparisons needed at all. The mirror tells us the future for free.
The only case that needs real work is when the mirror's answer would run past the right edge `r`. There the box's guarantee runs out — beyond `r` we have never compared anything against the prefix yet — so we set `Z[i]` to at least `r - i + 1` (the part we trust) and then extend by plain character-by-character comparison past `r`, exactly as the naive method would, but only over genuinely new ground. Whenever this extension pushes us past the old `r`, we slide the box forward to the new, further-right match. The same logic handles `i > r` (outside any box): there we just compare from scratch and open a fresh box.
Why it is linear
The cost analysis is the heart of the matter, and it is a lovely example of an aggregate argument rather than a per-step one. Split the work into two kinds. The first kind is the cheap copies, `Z[i] = Z[k]`, each costing O(1); there are at most `n` of them, so they total O(n). The second kind is the expensive character comparisons that actually read new characters when we extend past `r`. Counting these is the clever part.
- Every comparison that succeeds (a match) advances the right edge r by exactly one position, because we only ever compare characters strictly to the right of the current r.
- The edge r only moves rightward across the whole run and is bounded by n-1, so the total number of successful comparisons over the entire algorithm is at most n.
- Each position i triggers at most one failing comparison — the one that ends its extension — so failures are bounded by n as well.
- Adding it all up: O(n) copies plus at most n successes plus at most n failures gives O(n) total, independent of the alphabet size.
The key insight worth savoring: a character is read "freshly" (by a comparison that extends `r`) at most once over the entire run, because `r` never retreats. This is the same amortized flavor you may recall from dynamic-array doubling — any single `Z[i]` might do a lot of comparing, but the total across all `i` is capped by how far one ever-advancing pointer can travel. Worst case, best case, average case: it is O(n + m) every time, with no hidden dependence on how repetitive the strings are.
Z versus KMP, and what to watch for
The Z-array and the prefix function of KMP are close cousins: both encode self-overlap of a string, and you can mechanically convert one into the other in linear time. The practical difference is mostly taste. KMP processes the text in a true single streaming pass and never needs the text stored ahead of time, which suits matching against a live stream. The Z-approach needs the concatenation `P + '#' + T` in memory, but many people find the "how far does this re-match the prefix" idea easier to derive correctly from scratch under pressure, with fewer fencepost subtleties.
Beyond matching, the Z-array is a genuine multi-tool. It finds the longest substring that is also a prefix, detects the smallest period of a string (useful for compression and for spotting repeated tiles), and counts how many times a pattern occurs — all in linear time from one Z-pass. It also pairs naturally with heavier machinery: when you later meet the suffix array, you will see that the Z-array is the cheap, single-string special case of the same "how do parts of a string agree with other parts" question that those structures answer in full generality.