This post tries to explain the idea behind Manacher’s algorithm. It is written mainly for my own future reference so it might lack some clarity. I might improve upon it in the future when I have the time.
Manacher’s algorithm is a O(N) solution for finding the longest palindromic substring of a given string.
A palindrome is a sequence of symbols or elements that reads the same forward or reversed.
It is a dynamic programming problem. We let be the longest palindrome length for the palindrome that is centered at character i. We use a bottom up approach and fill the table dp. After that we find the maximum value in dp and retrieve the substring.
The transformation (preprocessing)
A clever trick to avoid splitting cases for odd and even as well as boundary checks is to transform the given string into one with delimiters added in between each character.
This will help us easily identify our palindrome because in our transformed string, the longest palindrome must start and end on a delimiter, and this maps nicely back to the index of the original string, providing an easy way to extract the substring. For example, to extract the palindrome bb, we note that it is a palindrome about index 12, and the left and right limits are 10 and 14 respectively. Dividing it by 2 gives us the indices of the original string, 5 and 7. And we can extract the substring by using s.substring(5,7).
The crux of the algorithm is noting that after calculating some , we can save calculations of for .
To see why. Let us denote the indices of left limit of the palindrome as L, right limit as R, and the center as C. Let T be the transformed string. Then let where is the range on either side of the palindrome centered at C.
Suppose we are now calculating where i is between C and R. There are two cases for this palindrome that is centered at i. Either it extends past R or it doesn’t. Suppose it doesn’t extend past R. Then by looking at the reflected point about C, that is dp[2C – i], we know that the palindrome centered at that point must not extend past L either. Therefore, . In the other case, the palindrome extends beyond R so we have to manually calculate the length of this palindrome centered at i. However, we can speed up this calculation by noting that since this extends past R, it’s length must be at least R-i, so we can start comparing characters after that distance.
This translate into code by setting dp[i] = min(dp[2C-i], R-i) and then updating dp[i] by trying to extend the palindrome.