Algorithms / Z Function
Least You Need to Know: Z-Function, Prefix Matches, and Pattern Search by Concatenation
The Z-function at position `i` stores the length of the longest substring starting at `i` that matches the whole string prefix. This lets you reason about repeated prefix structure and perform pattern search via concatenation.
The least you need to know
- Z-values measure prefix matches starting at each position.
- `Z[0]` is usually defined by convention and not the main focus.
- Pattern search can concatenate `pattern#text` and look for Z-values equal to the pattern length.
- The maintained Z-box reuses earlier comparisons for linear time.
- Z-function and prefix-function/KMP are related but different views of border structure.
Key notation
Z[i]
length of longest prefix match starting at position i
Z-box [L, R]
current interval matching the prefix
pattern#text
concatenated string for search using a separator
Tiny worked example
- For string `abacaba`, a position with `Z[i] = 3` means the next three characters match the prefix `aba`.
- To search for pattern `aba` in text `cabaaba`, build `aba#cabaaba`.
- Wherever the Z-value equals `3`, the pattern begins there in the text portion.
- The maintained Z-box avoids restarting comparisons from scratch.
Common mistakes
- Students sometimes think Z-values compare with the substring's own prefix instead of the whole string prefix.
- A separator not appearing in the pattern/text is needed in concatenation search.
- Z and prefix-function arrays encode related information but not the same entries.
How to recognize this kind of problem
- You need prefix-match lengths from every position.
- Pattern search is phrased as matching the whole pattern against many text suffixes.
- The solution mentions a Z-box or prefix matches.