Algorithms and data structures · Intermediate

The Z algorithm: compute prefix-match lengths

Reuse an established prefix-match interval to build a Z array in linear time and locate a pattern with a safe separator.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Define what each position records
  2. Reuse a bounded matching interval
  3. Search through a concatenated sequence
  4. Explain the linear bound precisely
  5. Ask Logeia about this articleCheck your understanding

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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path