Sign in to watch this lesson
Advanced - Strings Ā· 3:51
Manacher's Algorithm
A string can hold a quadratic number of palindromes, but two arrays of radii, d_odd and d_even, describe them all. Interleaving # turns both kinds into odd palindromes so one array does the job, and Manacher's algorithm fills it in linear time by mirroring arcs inside the rightmost palindrome found so far and growing only past its edge. We trace #a#b#c#b#c#b#a# arc by arc, watch the right edge move only forward, and count palindromes in a long long.
You will learn
- Describe all palindromic substrings with d_odd[i] and d_even[i] and explain why one number per centre is enough
- Use the # interleaving trick and convert back: d_odd[i] = d[2i+1] / 2 and d_even[i] = (d[2i] - 1) / 2
- Implement Manacher's algorithm with the rightmost palindrome (l, r): start from min(r - i, d[l + r - i]) and grow naively
- Prove the O(n) bound (the right edge only moves right) and count palindromic substrings safely in 64-bit