Manacher’s Algorithm: Longest Palindromic Substring

6 min readNov 2, 2022

Manacher’s algorithm finds longest palindromic substring in liner time. If a palindrome exists in another palindrome, this algorithm exploits mirrored property of palindromes and reuses already computed data before the center to find the longest palindrome centered at characters after the center. That way avoids unnecessary comparisons because it is not necessary to expand every center of a possible palindrome outwards.

Table of Contents· Brute Force Approach
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Mirrored Index
· Palindrome Radius
· How Does Manacher’s Algorithm Work?
  ∘ String Preprocessing
  ∘ PalindromeRadii Array
  ∘ Maximum Mirrored Radius
  ∘ 3 Cases to Reuse Precomputed Data
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python

Brute Force Approach

A palindrome can be either of even length or odd length. If it is of odd length, then the center of the palindrome is a character. Otherwise, the center of the palindrome is in between two characters.

The naive approach is to check every center of a potential palindrome and expand it towards the left and right. If it is a palindrome, update the current longest palindrome accordingly.

Graphical Explanation

Code Implementation

Complexity

Time: O(n²)
Space: O(n), slice the longest palindrome substring out of the string
n: the length of the input string

Golang

Python

Mirrored Index

A palindrome has a “mirrored” letter reflected across its center. The mirrored index of a given index can be computed by below equation.

center - mirrored_index = current_index - center
→ mirrored_index = 2 * center - current_index

Palindrome Radius

The radius of a palindrome is the number of characters can be expanded around the mirrored center.

How Does Manacher’s Algorithm Work?

Manacher’s Algorithm finds longest palindromic substring in liner time. It takes advantage of the mirrored property of palindromes and reuses already computed data to avoid redundant comparisons.

If there is a palindrome centered at index i, this algorithm exploits the longest palindrome that is already found before the center to calculate the longest palindromic substring after the center. That is, characters lies in the currently found palindrome after the center are not necessary to compare all characters in left and right side.

String Preprocessing

As we have mentioned, a palindrome can be either of even length or odd length. In order to handle both odd and even lengths, Manacher’s Algorithm inserts a bogus character between each character and at the two ends of the given string. Thus the total length of the processed string is 2*n + 1 that represents we have 2*n+1 centers to explore.

The inserted character can be any character unless the character is not appeared in the given string.

PalindromeRadii Array

An array is used to save the radius of the longest palindrome centered on each character in the string.

Maximum Mirrored Radius

Maximum mirrored radius is used to determine whether if the palindrome at the mirrored center lies inside the border of the old palindrome or not.

max mirrored radius 
= right border of the old palindrome - current center
= mirrored center - left border of the old palindrome

palindrome at mirrored center is completely inside the old palindrome

radius of mirrored center < max mirrored radius

palindrome at mirrored center extends exactly up to the border of the old palindrome

radius of mirrored center == max mirrored radius

palindrome at mirrored center extends outside the old palindrome

radius of mirrored center > max mirrored radius

3 Cases to Reuse Precomputed Data

When a palindrome lies in another palindrome(we call old palindrome to represent it here), we can reused data that already computed before the center.

case 1: palindrome at mirrored center is completely inside the old palindrome

The palindrome at current center will have the same length as the one at mirrored center.

palindromeRadii[current center] = palindromeRadii[mirrored center]

case 2: palindrome at mirrored center extends exactly up to the border of the old palindrome

The palindrome at current center is at least as long as the one at mirrored center. Keep expanding outward to find if the longer palindrome existed.

radius = max mirrored radius(temporary)
→ keep expanding outwards

case 3: palindrome at mirrored center extends outside the old palindrome

Because the old palindrome is the longest possible palindrome centered at the old center, so the character before and after it must be different.

palindromeRadii[current center] = max mirrored radius

Graphical Explanation

step1: string preprocessing
step2: initialize palindromeRadii array with the length of the preprocessed string
step3: iterate through every center/character in the string

step3.a: expand to the left and right simultaneously until we find the longest palindrome at the current center step3.b: save the radius of the longest palindrome in palindromeRadii arraystep3.c: find the longest palindrome from index center+1 based on already computed data at its mirrored index across the center
(identify 3 cases)