Manacher
Compute longest odd and even palindromic radii around every center in linear time.
Manacher
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Manacher's algorithm is the linear-time answer to ``tell me every longest palindrome centered here.'' It replaces the naive expand-around-center idea with a moving window that reuses symmetry inside the current rightmost palindrome.
When to Use It
Use it when:
the string is static,
palindrome centers matter,
you need longest palindromic substring, all palindromic radii, or many offline palindrome checks.
Core Idea
Maintain the rightmost palindrome currently known, with center \(c\) and right boundary \(r\). For a new center \(i\), look at its mirror \(j = 2c - i\).
If \(i < r\), the palindrome radius at \(i\) is at least the mirrored radius clipped by \(r - i\).
Then extend naively only beyond the current boundary.
This is done separately for odd and even centers.
Key Insight
The symmetry reuse is what makes the algorithm linear. Every time the while-loop expands, the global right boundary moves right, so the total number of character comparisons outside copied information is only \(O(n)\).
Worked Problem
Problem.
Given a string \(s\), find the longest palindromic substring and answer whether any chosen center has radius at least \(k\).
Why Manacher fits.
After one linear pass, you know the maximum odd radius \(d_1[i]\) and even radius \(d_2[i]\) for every center. Longest palindrome, counts of centered palindromes, and constant-time checks all fall out of those arrays.
Correctness Intuition
Inside the current rightmost palindrome, mirrored positions already tell you a safe lower bound on the new radius. The only uncertainty is beyond the right boundary, and every successful expansion pushes that boundary farther right.
Complexity Analysis
Both odd and even passes run in \(O(n)\), so the full algorithm is linear.
Implementation
The code returns:
odd[i]: radius of the longest odd palindrome centered at \(i\),even[i]: radius of the longest even palindrome centered between \(i-1\) and \(i\).
Common Pitfalls
Mixing the meaning of odd and even radii.
Off-by-one mistakes when converting a radius back into substring endpoints.
Forgetting that the radius counts characters on one side plus the center convention, not the whole length.
Variants / Extensions
Count all palindromic substrings by summing the radii.
Precompute arrays for constant-time palindrome checks on fixed centers.
Palindromic tree when insertions or distinct-palindrome bookkeeping are needed instead.
Practice Problems
Longest palindromic substring.
Count palindromic substrings.
Offline center-based palindrome queries.
References
Code
Contest-ready reference implementation for the idea explained above.
pair<vector<int>, vector<int>> manacher(const string& s) {
int n = (int)s.size();
vector<int> odd(n), even(n);
for (int left = 0, right = -1, i = 0; i < n; ++i) {
int radius = (i > right) ? 1 : min(odd[left + right - i], right - i + 1);
while (i - radius >= 0 && i + radius < n && s[i - radius] == s[i + radius]) {
++radius;
}
odd[i] = radius;
if (i + radius - 1 > right) {
left = i - radius + 1;
right = i + radius - 1;
}
}
for (int left = 0, right = -1, i = 0; i < n; ++i) {
int radius = (i > right) ? 0 : min(even[left + right - i + 1], right - i + 1);
while (i - radius - 1 >= 0 && i + radius < n && s[i - radius - 1] == s[i + radius]) {
++radius;
}
even[i] = radius;
if (i + radius - 1 > right) {
left = i - radius;
right = i + radius - 1;
}
}
return {odd, even};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.