Manacher's Algorithm (Longest Palindromic Substring)

Manacher's Algorithm (Longest Palindromic Substring)

Problem Description
Given a string, find its longest palindromic substring. For example, the longest palindromic substring of the string "babad" is "bab" or "aba". The algorithm's time complexity should be optimized to O(n).

1. Problem Analysis

The brute-force solution requires enumerating all substrings (O(n²)) and checking if they are palindromes (O(n)), resulting in a total complexity of O(n³). This can be optimized to O(n²) using the center expansion method (expanding outward from each character or gap). However, Manacher's algorithm further optimizes the complexity to O(n). Its core idea is to utilize the symmetry of palindromes to avoid redundant calculations.

2. Preprocessing: Unifying Odd and Even-Length Palindromes

Insert special characters (e.g., #) between each character of the original string, making all palindrome lengths odd.
Example:

  • Original string "aba" → "#a#b#a#" (new length is always odd).
  • Add different characters at the boundaries (e.g., ^ and $) to avoid boundary checks.

3. Core Concepts and Notation Definitions

  • Palindrome Radius Array p[i]: The palindrome radius centered at the i-th character of the new string (including itself).
    Example: # a # b # a #
    Index 0 1 2 3 4 5 6
    p[3] = 4 (palindrome #a#b#a# radius extends to the boundary).
  • Center C and Right Boundary R: The current known palindrome's furthest right boundary R and its corresponding center C.

4. Detailed Algorithm Steps

Iterate through each position i of the new string and calculate p[i]:

Case 1: i is to the left of the known palindrome's right boundary R

  • Find the symmetric point j of i about center C: j = 2*C - i.
  • If the palindrome radius p[j] of j does not exceed the left boundary of C (i.e., p[j] < R - i), then directly set p[i] = p[j].
    Principle: Since [C-R, C+R] is a palindrome and j is symmetric to i about C, when j's palindrome lies within C's palindrome range, i's palindrome must be identical.
  • If p[j] ≥ R - i, then first set p[i] = R - i, and then continue expanding outward.

Case 2: i is to the right of R

Symmetry cannot be utilized. Directly expand with i as the center, and simultaneously update C = i and R = i + p[i].

Expansion Operation

Compare whether the characters at i ± p[i] are the same. If they are, increment p[i] and continue until they differ.

5. Example Walkthrough

Take the string "babad" as an example:

  1. After preprocessing: ^#b#a#b#a#d#$ (ignoring boundary character details).
  2. Simplified traversal process:
    • i=1: Center b, R updates from 0 to 2, C=1.
    • i=2: Symmetric point j=0, p[0]=0, expansion yields p[2]=1.
    • i=3: Symmetric point j=1, p[1]=1, but i+p[j]=4 does not exceed R=2, so p[3]=p[1]=1. Then expansion reveals the palindrome #b#a#b#, updates p[3]=4, C=3, R=7.
  3. The final maximum p[i] corresponds to the palindrome substring #a#b#a# or #b#a#b#. Removing # yields "aba" or "bab".

6. Complexity and Correctness

  • Time Complexity O(n): Each character is expanded at most once, and R increases monotonically with traversal.
  • Space Complexity O(n): Stores the preprocessed string and the p array.

7. Key Summary

  • Preprocessing solves the odd/even length issue.
  • Utilizes the p array and (C, R) to avoid redundant expansions.
  • Actual implementation must pay attention to boundary handling and final result conversion (longest length = max(p[i]) - 1).

This algorithm efficiently solves the longest palindromic substring problem in linear time.