Lesson 272
Z-Algorithm & Manacher
Linear-Time String Magic
1:00Two linear-time string algorithms — the Z-array for prefix matching and Manacher's for finding the longest palindromic substring — both made O(n) by reusing a rightmost known window.
By the end, you can
- Define Z[i] and compute the full Z-array for a short string by hand.
- Explain how the Z-box [L, R] and the mirror initialization make the Z-algorithm O(n).
- Apply the Z-array to find all occurrences of a pattern P in text T in O(|P|+|T|) time.
- Explain why the naive expand-around-center palindrome algorithm is O(n²).
- Describe the # separator transformation used by Manacher's and why it unifies odd and even palindromes.
- Trace the mirror initialization step p[i] = min(p[2c−i], r−i) and explain the cap r−i.
- Recover the longest palindromic substring's length and start position from the p-array.
- Identify the shared O(n) argument behind both the Z-algorithm and Manacher's algorithm.
Up next in String Algorithms, Advanced DP & Competitive Techniques
