ayodhyya.comManacher's algorithm finds the longest palindromic substring in O(n) time by exploiting the symmetric nature of palindromes. It processes the string character by character, maintaining the center and right boundary of the current rightmost palindrome.
By inserting separators between characters (e.g., '|'), the algorithm handles both odd and even length palindromes uniformly, reducing both cases to odd-length palindrome expansion.
Manacher's Algorithm Implementation
The algorithm maintains an array P where P[i] stores the palindrome radius at position i in the transformed string. Using the mirror property, P[i] is initialized based on its symmetric counterpart within the current palindrome boundary.
Explicit expansion occurs when the mirror-based estimate reaches or exceeds the right boundary, ensuring correct radii are computed while maintaining linear time.
string manacher(string s) {
string T = "|";
for (char c : s) T += c, T += '|';
int n = T.size();
vector P(n, 0);
int center = 0, right = 0;
for (int i = 1; i < n - 1; i++) {
if (i < right)
P[i] = min(P[2 * center - i], right - i);
while (T[i + P[i] + 1] == T[i - P[i] - 1])
P[i]++;
if (i + P[i] > right)
center = i, right = i + P[i];
}
int maxLen = 0, idx = 0;
for (int i = 1; i < n - 1; i++)
if (P[i] > maxLen) maxLen = P[i], idx = i;
return s.substr((idx - maxLen) / 2, maxLen);
} Frequently Asked Questions
How does Manacher's achieve O(n) time?
Each intra-palindrome comparison uses cached mirror values. Explicit character expansion only happens when the palindrome extends beyond the current right boundary, which moves monotonically forward, limiting total comparisons to O(n).
Why insert separators between characters?
Separators ('|') transform the string so every palindrome has odd length in the transformed string, eliminating separate handling of even-length palindromes. The original palindrome length equals the radius in the transformed string.
Originally published on Ayodhyya. Last updated June 1, 2026.