Zfunctions

Z-functions, or Z-arrays, are a family of arrays used in string algorithms to describe how a string relates to its own prefix. For a string s of length n over some alphabet, the Z-function Z[0..n-1] assigns to each position i the length of the longest substring starting at i that matches a prefix of s. By convention, Z[0] is often set to n, reflecting that the whole string matches itself, although some definitions use Z[0] = 0.

Z-values can be computed in linear time using the Z-algorithm. It maintains a window [l, r], the segment of s that currently matches the prefix and ends furthest to the right. For i from 1 to n-1, if i ≤ r, set Z[i] = min(r - i + 1, Z[i - l]); otherwise Z[i] = 0. Then extend Z[i] by comparing s[Z[i]] and s[i + Z[i]] while they are equal, and update l and r when i + Z[i] − 1 > r. The total complexity is O(n) time and O(n) space. A naive approach tests all possible matches and runs in O(n^2).

Z-functions have several uses. They locate all occurrences of a pattern within a text by computing Z on the concatenated string pattern#text; they help identify all borders of a string; and they support efficient pattern matching in linear time. They are closely related to the prefix-function used in the Knuth–Morris–Pratt algorithm, and each can simulate the other with appropriate transformations.

Variants include generalized Z-functions for different alphabets or multiple strings, as well as adaptations for circular strings, palindromic substrings, or dynamic updates. In practice, the Z-algorithm is valued for its simplicity and linear worst-case performance in preprocessing and pattern-matching tasks.