Define what each position records
For a string s, Z[i] is the length of the match between the suffix starting at i and the prefix starting at zero. Use the convention Z[0]=0 here. For ababa, the array is [0,0,3,0,1]: the suffix at position 2 begins with aba, while the suffix at 4 matches only a. This differs from a prefix-function array, which records the longest proper border of each prefix. Understanding which positions and substrings the array describes prevents off-by-one mistakes and avoids incorrectly substituting one string-processing array for another.
Reuse a bounded matching interval
Maintain a known matching interval [L,R) with the farthest right endpoint discovered so far. Its contents equal the corresponding prefix of s. If i is inside that interval, Z[i−L] supplies reusable information, but only up to the remaining known length R−i. Start with min(Z[i−L],R−i), then compare new characters if that reaches the boundary. Blindly copying the entire earlier Z value can assert a match beyond the region already checked. The interval bound explains which comparisons may be skipped and which must actually be performed.
Search through a concatenated sequence
Construct P#T from pattern P, a separator absent from both inputs, and text T. For P=aba and T=ababa, combined positions 4 and 6 have Z values at least three, identifying text positions 0 and 2. Subtract m+1 from a combined position to recover the text index. A separator must not be chosen casually when arbitrary input may contain it; represent a sentinel outside the input alphabet when necessary. All matching positions can be found by inspecting the array, including occurrences that overlap rather than forming disjoint chunks of the text.
Explain the linear bound precisely
The right endpoint R never moves backward. New successful comparisons that extend it therefore total at most a linear number, while each position has only bounded additional initialization work. Building a Z array for a sequence of length N takes O(N) time and O(N) storage, with the latter also serving as output space when the complete array is returned. Assume constant-time comparison of sequence elements. Bytes, Unicode code points and normalized text elements give different position semantics. Empty strings and long repetitions are important boundary cases for both correctness and the claimed amortized behavior.