CONCEPT · International Master
Z-algorithm
also Z array · Z-function
Z[i] is the LCP of s and s[i..]. A rightmost window [l,r] makes the whole array O(n). Cousin of the prefix function.
Intuition
If you already matched a window that covers i, you can copy a prefix of Z and only extend at the boundary.
When to reach for it
- LCP with the whole string at every index
- String matching via pattern#text
- Period checks: Z[i]+i===n
Usual pits
- Z[0] conventions (0 vs n)
- Using one Z-array for LCP of two arbitrary suffixes
- Forgetting the separator in concat matching