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.
preprocess the String
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.
Main idea
i <= rightMax:
First Condition
In this condition, Len[i] = Len[j]. Because the rightest index of palindromic string at index i is less than the rightMax.
Second Condition
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.
i > rightMax
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.
Java code of this algorithm


If you have any questions, please leave a comment below.