What the Z array is
For a string, the Z array stores at each position the length of the longest substring starting there that also matches a prefix of the whole string. Position zero is usually left undefined or set to the full length.
The Z box trick
The clever part is reusing earlier work. We keep a window, often called the Z box, defined by two markers left and right that mark the rightmost match interval discovered so far.
- If the current index lies inside the box, a previously computed value gives a head start.
- We copy that value, capped so it does not run past the right edge, then extend by direct comparison only when needed.
Why it stays linear
Direct character comparisons only ever push the right marker forward, never backward. Since that marker advances at most to the end of the string, the total comparison work is linear in the string length.
Pattern matching use
To search for a pattern, build the string pattern then a separator then text, and compute the Z array. Any position whose Z value equals the pattern length marks a full occurrence.
Key idea
The Z array records prefix match lengths at every position, and a sliding match window lets it reuse prior comparisons so the whole array is built in linear time.