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.
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#textand 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
Worked example
- For string
abacaba, a position withZ[i] = 3means the next three characters match the prefixaba. - To search for pattern
abain textcabaaba, buildaba#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 it
- 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.
Next recommended lesson
Try Least You Need to Know: Binary Search on Answers and Monotone Predicates next for a nearby refresher.
Least You Need to Know: Binary Search on Answers and Monotone PredicatesRelated lessons
Keep going with nearby lessons in the same topic.