The definition
The Z function of a string assigns to each position the length of the longest stretch starting at that position that also matches a prefix of the whole string. The first position is special and is usually left as the full length or zero by convention.
Computing it with a window
A naive computation compares characters from each position against the prefix, which repeats work. The clever method keeps a window, the rightmost matching segment found so far, described by its left and right ends.
- If the current position lies inside that window, you already know a matching segment is present, so you can reuse the value from the mirrored earlier position as a head start.
- You then extend by direct comparison only past what the window guarantees, and slide the window forward when you reach further.
Because each character is examined a bounded number of times, the whole array is built in time proportional to the string length.
Uses
The Z function locates all occurrences of a pattern by concatenating the pattern, a separator, and the text, then scanning for values equal to the pattern length. It also helps with period detection and string comparison tasks.
Key idea
Reuse a sliding window of the rightmost match so each character is compared a bounded number of times.