Manacher's algorithm

Manacher's algorithm finds the longest palindromic substring of a given string in linear time. In the process, it builds a table with the length of the longest palindromic substring centered at each index in the string.

Code

s_prime = "#" + "#".join(s) + "#"
radii = [0] * len(s_prime)
center = 0
radius = 0

while center < len(s_prime):
    while (center - (radius + 1) >= 0 and center + (radius + 1) < len(s_prime) and
          s_prime[center - (radius + 1)] == s_prime[center + (radius + 1)]):
        radius = radius + 1
    
    radii[center] = radius

    old_center = center
    old_radius = radius
    center += 1

    radius = 0 
    while center <= old_center + old_radius:
        mirrored_center = old_center - (center - old_center)
        max_mirrored_radius = old_center + old_radius - center

        if radii[mirrored_center] < max_mirrored_radius:
            radii[center] = radii[mirrored_center]
            center += 1
        elif radii[mirrored_center] > max_mirrored_radius:
            radii[center] = max_mirrored_radius
            center += 1
        else:
            radius = max_mirrored_radius
            break

# 'radii' now contains the length of the longest palindrome centered at each index (of s_prime)
longest = max(radii)

# To get the substring of the longest palindrome
palindrome = ""
for i in range(len(radii)):
    if radii[i] == longest:
        palindrome = s_prime[i - longest + 1:i + longest:2]
        break

Explanation

Manacher's algorithm builds a table similar to the one below. It finds the length of the longest palindrome that is centered on each character.

Given the string: 'babadd'

First off, we preprocess the string by adding a dummy character between each index, and at the start and end. We do this so that we can use the same steps for both even and odd length substrings. For instance, the even substring 'aa' becomes 'a#a', which has an odd length.

It isn't technically necessary to modify the string. A version of the algorithm can be written that leaves the string as is; however, that will increase the complexity of the code.

The main loop has two repeating steps:

1. Find the radius of the longest palindrome centered at center
2. Find the lengths of each palindrome between center and center + radius .

This process allows us to take advantage of previously computed information about the string. Palindromes are mirrored, so the left half is reverse of the right half. This means that if we've identified sub-palindromes on the left half of our current palindrome, we can apply that information to the right half (hence step #2 iterating over the right half of the palindrome from step #1).

Step #1

Compare left and right characters and increase the radius as long as they are the same.

while (center - (radius + 1) >= 0 and center + (radius + 1) < len(s_prime) and
      s_prime[center - (radius + 1)] == s_prime[center + (radius + 1)]):
    radius = radius + 1
    
radii[center] = radius

Step #2

old_center = center
old_radius = radius
center += 1
radius = 0 
while center <= old_center + old_radius:
    mirrored_center = old_center - (center - old_center)
    max_mirrored_radius = old_center + old_radius - center

Imagine the following substring, with old_center marked in red and old_radius equal to 4. Since we've completed step one, we know that this is the longest palindrome centered at this index. To simplify things, this is what the example looks like without inserting the dummy characters.

center has been initialized to old_center + 1 , and will increment until it is greater than old_center + old_radius . So it will traverse the right half of the palindrome.

Now if we imagine that center (blue) has advanced to the second 'c', we can calculate the mirrored_center (green).

And here's what max_mirrored_radius looks like:

Now we run into the if statement with 3 special cases. They are as follows:

Case 1

if radii[mirrored_center] < max_mirrored_radius:
    radii[center] = radii[mirrored_center]
    center += 1

The radius of the palindrome at mirrored_center has already been computed (as has every index left of center ). In our example above, it is a radius of 1 (the longest palindrome is 'bcb'). This radius is less than max_mirrored_radius , indicating that the palindrome at mirrored_center is entirely contained within the palindrome at old_center (and it doesn't continue to the edge). Thus, the longest palindrome at center is the same as the one at mirrored_center .

We know this because we've seen the characters that border the mirrored palindrome, 'a' and 'p', and we know that they will also border our palindrome on the right.

Case 2

elif radii[mirrored_center] > max_mirrored_radius:
    radii[center] = max_mirrored_radius
    center += 1

Let's look at a different example. In this case, our old palindrome does not include the first or last character.

Let's add a center (blue), mirrored_center (green), and show the max_mirrored_radius (orange).

The palindrome at mirrored_center is 'axyxa'. Thus, the radius is 2 and therefore greater than the max_mirrored_radius .

Here are the longest palindromes at center and mirrored_center :

The palindrome at mirrored_center extends past the start of the old palindrome. Because the old palindrome is the longest it can be, we know that the characters directly before and after it are not the same (the 'a' and the 'b'). Hence, if the mirrored_center palindrome extends past the edge of the old palindrome, the palindrome at center cannot.

Case 3

else: # radii[mirrored_center] == max_mirrored_radius
    radius = max_mirrored_radius
    break

This else statement runs if radii[mirrored_center] equals max_mirrored_radius . In other words, if the palindrome at mirrored_center ends exactly at the bounds of the old palindrome.

Here is the previous example, but with the first and last characters swapped (this is very important!).

So our mirrored palindrome ends exactly at the left bound of the old palindrome.

What about the palindrome at center ? Well, we don't know the rightmost character yet (remember, this is outside of the old palindrome). We only know that it is not 'b'. If it is indeed an 'a', we can extend the palindrome at center .

But it could be another character, in which case we can't extend the palindrome.

Therefore, we break the loop, and go back to the first step. With our new center , we can now try to extend our palindrome as far as possible.

Example Problems

• 5. Longest Palindromic Substring (Medium)