✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-204

Manacher's Algorithm

Understand how Manacher's Algorithm finds the longest palindromic substring in linear time by reusing information about previously discovered palindrome boundaries.

Explanation

Overview

Manacher's Algorithm is a specialized string algorithm that finds the longest palindromic substring of a given string in O(n) time. It uses symmetry around palindrome centers and previously calculated palindrome radii to avoid repeatedly expanding the same regions.

Key concepts

Palindromic substrings; Palindrome centers; Symmetry; Mirror positions; Palindrome radius; Linear-time processing

Complexity

time: O(n), because the right boundary of the explored palindrome region only moves forward.; space: O(n) for the transformed string and palindrome-radius array.; variables: n is the length of the original input string.

Example

input: babad; possibleLongestPalindromes: bab; aba; longestLength: 3; explanation: Both bab and aba are valid longest palindromic substrings. The algorithm can return either one.

Pseudocode

function manacher(text):
transformed = addSeparators(text)
P = array of size length(transformed) filled with 0
center = 0
right = 0
for i = 0 to length(transformed) - 1:
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while characters around i match:
P[i] += 1
if i + P[i] > right:
center = i
right = i + P[i]
return longestPalindromeFrom(P, transformed)

Applications

Text analysis.; Palindrome detection.; Bioinformatics.; Sequence analysis.; Competitive programming.; String-processing research.

Advantages

Finds a longest palindromic substring in linear time.; Handles odd-length and even-length palindromes in a unified way after transformation.; Avoids redundant palindrome expansion.; Uses a predictable linear amount of additional memory.

Example or application

Input

babad

Possible Longest Palindromes

  • bab

  • aba

Longest Length

3

Explanation

Both bab and aba are valid longest palindromic substrings. The algorithm can return either one.

Definition

Manacher's Algorithm is a specialized string algorithm that finds the longest palindromic substring of a given string in O(n) time. It uses symmetry around palindrome centers and previously calculated palindrome radii to avoid repeatedly expanding the same regions.

Fundamental Concepts

Palindrome

A sequence that reads the same forward and backward.

Palindromic Substring

A contiguous section of a string that is a palindrome.

Center

The position around which a palindrome is symmetric.

Radius

The number of characters a palindrome extends outward from its center under the algorithm's representation.

Left Boundary

The leftmost boundary of the current rightmost palindrome.

Right Boundary

The rightmost boundary of the current rightmost palindrome.

Mirror Position

The position symmetric to the current center relative to the known palindrome center.

Algorithm Approach

  • Transform the input string by inserting separators between characters so odd-length and even-length palindromes can be handled uniformly.

  • Maintain the center and right boundary of the rightmost palindrome discovered so far.

  • For each transformed position, use its mirrored position to initialize a palindrome radius when it lies within the known boundary.

  • Expand the palindrome while the characters on both sides match.

  • Update the current center and right boundary whenever a palindrome extends farther.

  • Track the maximum radius and convert the result back to the original string.

Pseudocode

function manacher(text):
transformed = addSeparators(text)
P = array of size length(transformed) filled with 0
center = 0
right = 0
for i = 0 to length(transformed) - 1:
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while characters around i match:
P[i] += 1
if i + P[i] > right:
center = i
right = i + P[i]
return longestPalindromeFrom(P, transformed)

Complexity

Time

O(n), because the right boundary of the explored palindrome region only moves forward.

Space

O(n) for the transformed string and palindrome-radius array.

Variables

n is the length of the original input string.

Key Concepts

  • Palindromic substrings

  • Palindrome centers

  • Symmetry

  • Mirror positions

  • Palindrome radius

  • Linear-time processing

Advantages

  • Finds a longest palindromic substring in linear time.

  • Handles odd-length and even-length palindromes in a unified way after transformation.

  • Avoids redundant palindrome expansion.

  • Uses a predictable linear amount of additional memory.

Limitations

  • The mirror-position logic can be difficult for beginners.

  • Care is required when transforming the string and converting indices back.

  • The algorithm finds contiguous palindromic substrings, not the longest palindromic subsequence.

  • It is specialized for palindrome analysis rather than general pattern matching.

Applications

  • Text analysis.

  • Palindrome detection.

  • Bioinformatics.

  • Sequence analysis.

  • Competitive programming.

  • String-processing research.

Related Topics

  • Dynamic Programming

  • Longest Common Subsequence

  • String Algorithms

  • Pattern Matching

Practice Question

What is the length of the longest palindromic substring in the string abacdfgdcaba?

Practice Answer

3, because aba is a longest palindromic substring.

Learning Objectives

  • Explain the central idea and purpose of manacher's algorithm.

  • Identify the assumptions, inputs, and conditions relevant to manacher's algorithm.

  • Evaluate an application of manacher's algorithm for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • String Algorithms and Pattern Matching

Suggest a correction or source · More in Algorithms & Data Structures