concept · INFO-CS-ADS-204Manacher'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
Possible Longest Palindromes
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.
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