Manacher's Algorithm

Manacher's algorithm is a linear-time sequence analysis procedure within computation and algorithms that computes the maximal palindromic substring centered at every position of a string S of length n in O(n) worst-case time and O(n) space. Published by Glenn K. Manacher in 1975—originally to test online whether a string begins with an initial palindrome—and subsequently generalized by Apostolico, Breslauer, and Galil (1995) to recover all centered maximal palindromes simultaneously, the algorithm resolves both the longest palindromic substring problem and the complete enumeration of up to 2n + 1 palindromic centers in a single left-to-right scan.

A naive center-expansion search tests each of the n character centers (for odd-length palindromes) and n − 1 inter-character boundaries (for even-length palindromes) independently, requiring Θ(n²) character comparisons on repetitive strings such as "aaaa...a". Manacher's algorithm eliminates redundant expansions in two ways: first, it interleaves sentinel separator characters "#" between every adjacent pair of characters so that both odd-length and even-length palindromes become odd-length palindromes in a transformed string T of length 2n + 1; second, it tracks the center C and right boundary R = C + P[C] of the rightmost palindrome discovered so far, copying or lower-bounding the palindrome radius P[i] at any index i < R from its reflection i' = 2C − i across C.

Unifying Odd and Even Palindromes via "#"-Interleaving

In a string S[0 .. n − 1], an odd-length palindrome such as "aba" is centered on a character index, whereas an even-length palindrome such as "abba" is centered on the boundary between two adjacent indices. To avoid maintaining two separate loops and radius arrays, Manacher's algorithm constructs an augmented string T of length N = 2n + 3 by inserting a special separator character "#" ∉ Σ before, between, and after every character of S, bookended by distinct start and end sentinels "@" and "#":

For example, S = "abba" is transformed into T = "^#a#b#b#a##". Under this transformation:

• Every odd-length palindrome in S centered at S[k] maps to an odd-length palindrome in T centered at the character position 2k + 2 (bookended by "#" on both ends).
• Every even-length palindrome in S centered between S[k] and S[k + 1] maps to an odd-length palindrome in T centered at the separator position 2k + 3 (also bookended by "#" on both ends).

The Palindromic Radius Array P[i]

For each index i ∈ {1, …, 2n + 1} in T, let the palindromic radius P[i] denote the largest non-negative integer r such that the substring T[i − r .. i + r] is a palindrome:

A remarkable algebraic property of the "#"-interleaved representation is that the radius P[i] in T equals the exact character length of the corresponding maximal palindrome in the original string S. Specifically, a palindrome of radius P[i] in T spans 2P[i] + 1 characters in T, of which P[i] + 1 are "#" separators and P[i] are original characters from S, starting at index ⌊(i − P[i] − 1) / 2⌋ in S.

Reflection Geometry Inside [L, R]

As the algorithm scans index i from 1 to 2n + 1, it maintains the center C and right endpoint R = C + P[C] of the palindrome with the maximum right boundary R encountered among all previous centers 1 ≤ j < i. The corresponding left boundary of this outer palindrome is L = 2C − R = C − P[C].

Whenever the current index i lies within the rightmost palindrome (i < R), its mirror index reflected across center C is:

Because the outer substring T[L .. R] is a palindrome centered at C, every character at offset +d from C equals the character at offset −d from C. Consequently, any sub-palindrome centered at i' that stays completely within [L, R] is reflected verbatim around i:

1. Case 1 (Mirror Palindrome Strictly Contained: P[i'] < R − i): The left endpoint of the palindrome centered at i' is i' − P[i'] > L. Because the mismatching boundary characters T[i' − P[i'] − 1] ≠ T[i' + P[i'] + 1] both lie inside [L, R], reflection across C implies that T[i + P[i'] + 1] ≠ T[i − P[i'] − 1]. Therefore P[i] = P[i'] with zero character comparisons.
2. Case 2 (Mirror Palindrome Touches or Extends Past L: P[i'] ≥ R − i): Reflection guarantees that the substring around i of radius R − i is a palindrome, so P[i] ≥ R − i. However, because characters beyond index R lie outside the outer palindrome centered at C, symmetry says nothing about T[R + 1]. The algorithm initializes P[i] ← R − i and expands outward by comparing T[i + P[i] + 1] against T[i − P[i] − 1], updating C ← i and R ← i + P[i] whenever i + P[i] exceeds R.
3. Case 3 (Outside the Active Boundary: i ≥ R): Initialize P[i] ← 0, expand outward from center i via character comparisons, and update C ← i and R ← i + P[i].

Compact Single-Formula Implementation and Amortized Bound

All three cases collapse into a single initialization statement followed by a while loop:

Every successful iteration of the character-comparison while loop (T[i + 1 + P[i]] = T[i − 1 − P[i]]) checks a character at index i + 1 + P[i] > R and strictly increments the rightmost boundary R by 1. Because R starts at 0, never decreases, and cannot exceed 2n + 1, at most 2n + 1 successful character comparisons occur across the entire algorithm, plus at most one mismatch comparison per center i (protected from bounds checks by the distinct sentinels "@" and "#"). Thus Manacher's algorithm performs fewer than 4n + 2 comparisons in total, running in O(n) time.

Distinct Palindromes and the Eertree Connection

A corollary of Manacher's mirror-symmetry invariant proved by Droubay, Justin, and Pirillo (2001) states that a string of length n contains at most n + 1 distinct palindromic substrings (including the empty string). Whenever extending the string by one character S[k] creates a new right endpoint R, at most one new distinct palindrome can emerge—namely the longest palindromic suffix of S[0 .. k], because any shorter palindromic suffix is already reflected inside the longer one via mirror index i' = 2C − i. This observation forms the basis of the Eertree (or palindromic automaton, Rubinchik & Shur, 2015).

Computational Biology and Nucleic Acid Hairpin Loops

In bioinformatics and molecular genetics, genomic and transcriptomic sequences frequently form palindromic inverted repeats—regions where a single-stranded RNA or DNA sequence matches the reverse complement of an adjacent downstream segment (e.g., 5′-GACCT…AGGTC-3′). Replacing equality comparisons T[a] = T[b] outside the center with Watson–Crick complement comparisons (A ↔ T/U, C ↔ G) in the even-center pass of Manacher's algorithm enables linear-time scanning of whole chromosomes for stem-loop hairpins, CRISPR clustered regularly interspaced short palindromic repeat arrays, and restriction endonuclease recognition sites, complementing suffix array and Z algorithm sequence indexes.

Why is it unnecessary to explicitly construct the "#"-interleaved string in memory?

Although interleaving "#" characters simplifies exposition, a production implementation can compute two radius arrays directly over the original string S[0 .. n − 1]: d₁[i] storing the number of palindromes of odd length centered at i, and d₂[i] storing the number of palindromes of even length centered between i − 1 and i. Alternatively, a single loop from z = 0 to 2n − 2 can index S[z / 2] on even indices and treat odd indices as virtual separators without allocating a 2n + 3 character buffer.

How does Manacher's algorithm compare with the Z algorithm?

Both algorithms achieve O(n) time by maintaining the rightmost interval [L, R] discovered so far and looking up a precomputed value inside that interval to avoid re-scanning characters. Whereas the Z algorithm maintains a substring that matches a prefix of S and uses the translation offset k' = k − L, Manacher's algorithm maintains a palindromic substring centered at C and uses the reflection offset i' = 2C − i.

Can Manacher's algorithm find all palindromic substrings of a string in O(n) time?

A string of length n can contain up to n(n + 1) / 2 palindromic substrings (for example, "aaaa...a"), so listing every palindromic substring individually requires Ω(n²) output time in the worst case. However, the array P[1 .. 2n + 1] computed by Manacher's algorithm in O(n) time provides a complete compressed representation of all palindromic substrings: a substring S[l .. r] is a palindrome if and only if the radius at its corresponding center in T satisfies P[l + r + 2] ≥ r − l + 1, allowing O(1)-time palindrome queries for any interval [l, r] and summing ∑ ⌈P[i] / 2⌉ to count all palindromic substrings in O(n) time.

1. Manacher, G. (1975). "A new linear-time 'on-line' algorithm for finding the smallest initial palindrome of a string." Journal of the ACM, 22(3), 346–351. https://doi.org/10.1145/321892.321896
2. Apostolico, A., Breslauer, D., & Galil, Z. (1995). "Parallel detection of all palindromes in a string." Theoretical Computer Science, 141(1–2), 163–173. https://doi.org/10.1016/0304-3975(94)00083-U00083-U)
3. Droubay, X., Justin, J., & Pirillo, G. (2001). "Episturmian words and some constructions of de Luca and Rauzy." Theoretical Computer Science, 255(1–2), 539–553. https://doi.org/10.1016/S0304-3975(99)00320-500320-5)
4. Rubinchik, M., & Shur, A. M. (2018). "EERTREE: An efficient data structure for processing palindromes in strings." European Journal of Combinatorics, 68, 249–265. https://doi.org/10.1016/j.ejc.2017.07.021