Z-Function Prefix Matches

The Z-function is a linear-time string matching algorithm that computes the longest common prefix (LCP) between a string and each of its suffixes. For a string s of length n, the Z-array Z[i] stores the length of the LCP of s and s[i..n-1]. By definition, Z[0] = 0 in this specific convention.

Interactive Demonstration

Open the Z-Function interactive experiment. You can use the Text, Step, Finish, and Reset controls.

1. Enter the text abacaba and click Step.
2. Observe how the algorithm maintains a half-open window [l, r) representing the rightmost matched prefix segment.
3. When i falls within [l, r), it initializes the current match length from Z[i - l], avoiding redundant comparisons.
4. Click Finish to quickly reveal the final array [0, 0, 1, 0, 3, 0, 1] without viewing intermediate steps.
5. Invalid characters such as numbers or uppercase letters trigger an error and prevent search continuation.