Z-Function for Pattern Search
Match prefixes across the string.
Another Matching Tool
The Z-function is a clean alternative to KMP for pattern search. Many find it easier to reason about. ✨
What z[i] Means
For each index, z[i] is the length of the longest substring starting at i that also matches a prefix of the whole string.
All lessons in this course
- KMP Prefix Function
- Polynomial String Hashing
- Z-Function for Pattern Search
- Tries for Prefix Lookups