📜 WAYPOINT LESSON
The Z-Function
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 166 of 281
z[i] is the longest common prefix of s and s[i:]; the z-box invariant reuses earlier matches so the whole array builds in O(n).
Matches that remember
The [l, r) z-box is the rightmost match window seen so far. If i sits inside it, z[i] starts at min(r - i, z[i - l]) — earlier work copied forward — then only the unmatched tail is compared. Periodic strings make z[i] collapse dramatically: that collapse IS the period detection.