Z-Function Prefix Matches
Explore how a shared prefix can reappear inside a string and how a moving window reuses earlier matches.
By Riano · Published · Updated · Report a correction
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.
Independent Original Case
Consider computing the Z-array for the text aabaaab independently. We initialize Z[0] = 0.
i=1:s[1..6]isabaaab. LCP withaabaaabis 1 (a).Z[1] = 1.i=2:s[2..6]isbaaab. LCP withaabaaabis 0.Z[2] = 0.i=3:s[3..6]isaaab. LCP withaabaaabis 2 (aa).Z[3] = 2.i=4:s[4..6]isaab. LCP withaabaaabis 3 (aab).Z[4] = 3.i=5:s[5..6]isab. LCP withaabaaabis 1 (a).Z[5] = 1.i=6:s[6..6]isb. LCP withaabaaabis 0.Z[6] = 0.
The resulting Z-array is 0, 1, 0, 2, 3, 1, 0.
Interactive Demonstration
Open the Z-Function interactive experiment. You can use the Text, Step, Finish, and Reset controls.
- Enter the text
abacabaand click Step. - Observe how the algorithm maintains a half-open window
[l, r)representing the rightmost matched prefix segment. - When
ifalls within[l, r), it initializes the current match length fromZ[i - l], avoiding redundant comparisons. - Click Finish to quickly reveal the final array
[0, 0, 1, 0, 3, 0, 1]without viewing intermediate steps. - Invalid characters such as numbers or uppercase letters trigger an error and prevent search continuation.
The reusable-box computation is linear. This bounded explorer stores a full Z-array snapshot per index, so the teaching frames use quadratic storage; they are separate from the core algorithm.
Known Limitations
The implementation enforces a text length limit of 12 characters and restricts inputs to lowercase English ASCII letters. Empty strings are gracefully handled, producing an empty result array. While this linear Z algorithm runs efficiently with O(n) comparisons, visual stepping through every character matching operation restricts maximum text length for a readable UI trace. It avoids recursive structures like suffix trees, providing exact matches instead of fuzzy or approximate alignments.
References
The Z-function is a well-established foundational algorithm. Our direct direct substring comparisons independently derive our arrays.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Z-Function Prefix Matches module.
Try Z-Function Prefix Matches on Riano →