Manacher’s Algorithm is used to solve the problem of longest Palindromic Substring problem. Compared with brute force solution (which time complexity is O(N^3), and space complexity is O(N^3)), Manacher’s Algorithm is much better. (Time complexity is O(N), space complexity is O(N)). This post is going to illustrate this amazing algorithm.
When we are solving this problem, we may need to classify different situation: 1. String.length() is odd 2. String.length() is even
We can preprocess the origin string to make it easier.
The solution is:
The reason for the first element “!” is to avoid crossing the border.For example, when matching
#b#o#b#, we will match to index -1 and index 7. And it
Then the main idea of this algorithm is:
we need to create another array to store the number of palindromic substring. For example:
In this example, I call that array “p”. And the max(Len) -1 should be the length of the longest Palindromic Substring. When our question becomes -> how to calculate this array Len.
In this condition, Len[i] = Len[j]. Because the rightest index of palindromic string at index i is less than the rightMax.
In this condition, We know that Len[i] <= Len[j], so when we are calculating Len[i], it will be quicker if we can use the known information of Len[j]. What we need to do is to compare the expanded string to check whether we can expand this palindromic Substring.
In this condition, we know i is not in the range of the palindromic string at index middlePoint. So we know nothing of index i. What we need to do is compare the expanded string and check. Also, update the middlePoint and rightMax after the caculation.
If you have any questions, please leave a comment below.