Manacher’s Algorithm

Prerequisite: Expand Around The Centre.

Manacher’s algorithm optimizes the “Expand Around The Centre” solution by using some insights into how palindromes work.

Let C be the center of the longest-length palindrome we have encountered till now. And let L and R be the left and right boundaries of this palindrome, i.e., the left-most character index and the right-most character index, respectively.

Take an example: STR = “abacabacabb”

When going from left to right, when i is at index 1, the longest palindromic substring is “aba” (length = 3).

The longest palindromic substring for the given string is 9 when the palindrome is centered at index 5:

CURR_L: For any palindrome centered at a center C the CURR_L of the mirror of the given index j in the left direction, the mirror of index j is j’ such that

J’ = 2*C - J

For palindrome “abacaba”, the mirror of j is j’ and the mirror of j’ is j.

for some j, its mirror j’ for palindrome “abacaba”

We try to “expand” the palindrome at each i (CURR_R). When I say the word expand, it means that I’ll check whether there exists a palindrome centered at i and if there exists one, I’ll store the “expansion length” to the left or the right in a new array called LEN_ARR[] or P[] array. If the palindrome at i expands beyond the current right boundary r, then c is updated to i and new l, r is found and updated.

Let’s take the previously discussed palindrome “abacaba” which is centered at i = 3.

P[i] = 3 as expansion length for palindrome centered at i is 3

Hence, the LEN_ARR[] or P[] array stores the expansion length of the palindrome centered at each index. But we don’t need to manually go to each index and expand to check the expansion length every time. This is exactly where Manacher’s algorithm optimizes better than brute force by using some insights on how palindromes work. Let’s see how the optimization is done.

Let’s see the P[] array for the string “abacaba”.

When i = 4, the index is inside the scope of the current longest palindrome, i.e., i < r. So, instead of naively expanding at i, we want to know the minimum expansion length that is certainly possible at i so that we can expand on that minimum P[i] and see, instead of doing from the start. So, we check for mirror i’. As long as the palindrome at index i’ does NOT expand beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is P[i’].

Here we are only talking about the minimum possible expansion length, the actual expansion length could be more and, we’ll find that out by expanding later on. In this case, P[4] = P[2] = 0. We try to expand but still, P[4] remains 0.

If the palindrome at index i’ expands beyond the left boundary (l) of the current longest palindrome, we can say that the minimum possible expansion length at i is r-i.

For example: STR = “acacacb”

In the above diagram, palindrome centered at i’ expands beyond the left boundary

So, P[4] = 5–4 = 1

Keep Updating P[i] to the minimum certainly possible expansion length. Now the only thing left is to expand at i after P[i], so we check characters from the index (P[i] + 1) and keep expanding at i.

If this palindrome expands beyond r, update c to i and r to (i + P[i]). The P[] or LEN_ARR[] array is now filled, and the maximum value in this array gives us the longest palindromic substring in the given string.
 

Algorithm:

• Initialize a variable ‘N’ to store the length of ‘STR’.
• If ‘N’ is less than 2, return ‘STR’.
• Set ‘N’ as 2 * ‘N’ + 1.
• Initialize a list ‘LENARR’.
• Set ‘LENARR’[‘0’] as 0.
• Set ‘LENARR’[‘1’] as 1.
• Initialize ‘CENTER’ as 1, ‘CENTERR’ as 2, ‘CURRR’ as 0, ‘CURRL’,  ‘MAXLPSLENGTH’ as 0, ‘MAXPLSCENTERPOSITION’ as 0, ‘START’ as -1, ‘END’ as -1 and ‘DIFF’ as -1.
• Iterate ‘CURRR’ in 2 to ‘N’.
  • Set ‘CURRL’ as 2 * ‘CENTER’ - ‘CURRR’.
  • Add 0 to ‘LENARR’.
  • If currentRightPosition ‘CURRR’ is within centerRightPosition ‘CENTERR’, set ‘LENARR’[‘CURRR’] as the minimum of ‘LENARR’[‘CURRL’] and ‘DIFF’.
  • Expand palindrome centered at currentRightPosition ‘CENTER’. Here for odd positions, we compare characters, and if match then increments LPS Length by ONE. If even position, we just increment LPS by ONE without any character comparison.
  • If ‘CURRR’ + ‘LENARR’[‘CURRR’]  is greater than ‘CENTERR’
    • Set ‘CENTER’ as ‘CURRR’.
    • Set ‘CENTERR’ as ‘CURRR’ + ‘LENARR’[‘CURRR’].
• Set ‘START’ as (‘MAXPLSCENTERPOSITION’ - ‘MAXLPSLENGTH’)/2.
• If ‘MAXLPSLENGTH’ is equal to 1:
  • Return substring of ‘STR’ from index 0 to 1.
• Return substring of ‘STR’ from index ‘START’ to ‘START’ + ‘MAXLPSLENGTH’.

O(N), where N is the length of the string. 

Since the manacher’s algorithm takes O(N) time, the overall time complexity will be O(N).

O(N), where N is the length of the string.

We have created a LEN_ARR[] or P[] array,. which takes O(N), so the overall space complexity will be O(N).