Sign in to watch this lesson
Advanced - Strings Ā· 4:47
Z-Function
The Z-function stores, for every position, how much of the string starts again right there: the longest common prefix of s and the suffix at i. We compute it live for aaabaab with the rightmost match box [l, r), mirroring earlier values and clamping them to the box, show what goes wrong without the clamp on aaaabaa, and prove the scan linear because every successful comparison pushes r to the right. Then pattern search, borders and periods all fall out of one Z array.
You will learn
- Define z[i] as the longest common prefix of s and s[i..] (z[0] = 0 by convention) and compute it by hand for short strings
- Implement the O(n) Z-algorithm with the half-open box [l, r): initialise z[i] = min(r - i, z[i - l]) inside the box, then extend naively
- Explain why the clamp to r - i is required and why the total work is at most about 2n comparisons
- Use Z on p + separator + t to find all matches, and use i + z[i] = n to list borders and the shortest period