Skip to content
AfluidityAlgorithm Atlas
Pattern MatchingAll categories
CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Manacher's Algorithm

Finds the longest palindromic substring of any string in linear O(n) time by reusing palindrome radii across center reflections.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Pattern Matching
Difficulty
Intermediate
Family
Palindrome & String Structure
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
2
Relationships
2
Code example
Not ready
Visualization
Ready
Aliases
Manacher Palindrome Search, Linear-Time Longest Palindromic Substring

Overview

Manacher's Algorithm inserts sentinel separators between characters so even- and odd-length palindromes share uniform centers, then maintains the rightmost palindrome boundary to mirror previously computed radii in O(n) time.

Core Concepts

palindrome symmetrycenter-radius arrayrightmost palindrome boundarysentinel insertion

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Manacher's Algorithm across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(n)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(n)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(n)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Linear-time O(n) palindrome search algorithm that finds the longest palindromic substring and all palindrome center radii in a string by mirroring radii across the rightmost palindrome boundary.
  • Use it when strings contain long repeated or symmetric runs where naive center expansion degrades to quadratic time.

When Not to Use

  • Avoid it when approximate or gapped palindromes with mismatches are required; use sequence alignment or suffix-tree LCA instead.

What It Does

  • Manacher's algorithm computes palindrome radii in a single O(n) pass using mirror symmetry.
  • Evaluates `mirror(i) = 2C - i` (Mirror index) using O(n) auxiliary storage.

Use Cases

  • Linear-time O(n) palindrome search algorithm that finds the longest palindromic substring and all palindrome center radii in a string by mirroring radii across the rightmost palindrome boundary.
  • Use it when strings contain long repeated or symmetric runs where naive center expansion degrades to quadratic time.

Inputs

  • Input string S of length n

Outputs

  • Longest palindromic substring and array of palindrome radii P[0..2n]

Key Formulas (2)

Mirror index

mirror(i) = 2C − i
mirror(i) = 2C - i

Reflects position i across the current palindrome center C.

Radius lower bound

P[i] ≥ min(R − i, P[2C − i]) for i < R
P[i] >= min(R - i, P[2C - i]) for i < R

Reuses the mirrored palindrome radius bounded by the rightmost palindrome edge R.

Pseudocode

  1. 1.If len(S) == 0: return ''
  2. 2.Transform S into T = '#' + '#'.join(S) + '#' of length m = 2 * len(S) + 1
  3. 3.Initialize radius array P[0..m-1] = 0, center C = 0, right boundary R = 0
  4. 4.For each index i from 0 to m - 1:
  5. 5. If i < R: P[i] = min(R - i, P[2 * C - i])
  6. 6. While i - P[i] - 1 >= 0 and i + P[i] + 1 < m and T[i - P[i] - 1] == T[i + P[i] + 1]:
  7. 7. P[i] = P[i] + 1
  8. 8. If i + P[i] > R: C = i; R = i + P[i]
  9. 9.Find bestCenter = argmax_i P[i] and maxLen = P[bestCenter]
  10. 10.Compute start = (bestCenter - maxLen) // 2 and return S[start : start + maxLen]

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. If len(S) == 0: return ''
  2. Transform S into T = '#' + '#'.join(S) + '#' of length m = 2 * len(S) + 1
  3. Initialize radius array P[0..m-1] = 0, center C = 0, right boundary R = 0
  4. For each index i from 0 to m - 1:
  5. If i < R: P[i] = min(R - i, P[2 * C - i])
  6. While i - P[i] - 1 >= 0 and i + P[i] + 1 < m and T[i - P[i] - 1] == T[i + P[i] + 1]:
  7. P[i] = P[i] + 1
  8. If i + P[i] > R: C = i; R = i + P[i]
  9. Find bestCenter = argmax_i P[i] and maxLen = P[bestCenter]
  10. Compute start = (bestCenter - maxLen) // 2 and return S[start : start + maxLen]

Canonical Example

Input
S = 'babad'
Output
'bab' (or 'aba', length 3)
Explanation
Manacher's algorithm computes palindrome radii in a single O(n) pass using mirror symmetry.

Implementation Notes

  • In T = '#' + '#'.join(S) + '#', positions i - d and i + d always have identical parity (their difference 2*d is even), so separator indices are only ever compared with separator indices and character indices with character indices—even if '#' appears inside S.
  • Maintain center C and rightmost boundary R = C + P[C]; the while loop advances R at most 2n + 1 times across the entire run.

Common Pitfalls

  • Omitting explicit bounds checks (i - P[i] - 1 >= 0 and i + P[i] + 1 < len(T)) in the expansion loop raises IndexError in Python and loops infinitely in JavaScript because T[-1] === T[len(T)] === undefined.
  • Extracting the palindrome by stripping '#' characters from T (e.g. replace('#', '')) corrupts inputs that naturally contain '#'; always slice S directly via start = (bestCenter - maxLen) // 2 and S[start : start + maxLen].
  • Using sentinel characters (such as '^' and '$') without checking that they do not appear in the input string S can cause false matches at the boundaries.

Interactive Mechanism Walkthrough & State Debugger

Sequence Window & Automaton Alignment

Finds the longest palindromic substring of any string in linear O(n) time by reusing palindrome radii across center reflections.

Input:ABABABCABAB
Window:ABAB
shift offset s0
window T[s..s+m]"ABAB"
pattern P"ABAB"
alignmentExact Match ✓
Step 1 of 10: If len(S) == 0: return ''
step-walkthrough

Sources (1)

What each reference supports for this entry.

Manacher (1975) — A New Linear-Time On-Line Algorithm for Finding the Smallest Initial Palindrome of a String

Paper

Original JACM paper introducing linear-time palindrome radius mirroring.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toSuffix Automaton

Pattern Matching · Extended

Manacher's algorithm specializes in linear-time palindrome radii with minimal overhead.

Compare with this
Conceptual neighborZ Algorithm

Pattern Matching · Core

Both maintain a rightmost matched interval [L, R] to reuse prior comparisons in O(n) time.

Compare with this

Relationships

View full relationship page
Conceptual neighborZ Algorithm

Both maintain a rightmost matched interval [L, R] to reuse prior comparisons in O(n) time.

Alternative toSuffix Automaton

Manacher's algorithm specializes in linear-time palindrome radii with minimal overhead.

Related Algorithms

Z AlgorithmSuffix Automaton

Tags

Pattern MatchingStringsLinear Time