Manacher's Algorithm
Manacher computes the palindrome radius at every center in linear time by mirroring radii inside the rightmost known palindrome.
Why radii are enough
A string can contain Θ(N²) palindromic substrings, so listing them cannot be linear. Manacher stores a radius per center; every shorter radius with the same parity is also a palindrome, compactly representing all occurrences.
Odd radii center on a character and even radii center between characters. Separate d1/d2 arrays avoid transformed-string sentinels; inserting separators offers one unified array but requires careful mapping back to original indexes.
- Output radii, not every substring
- Odd centers are characters
- Even centers lie between characters
The maintained palindrome
Keep the palindrome [L,R] whose right endpoint is farthest right. For center i inside it, mirror j=L+R−i. Initialize the new radius from the mirror but cap it by the distance to R because the mirror proves nothing outside the known boundary.
Expand character by character beyond that seed. If the palindrome reaches farther right, update L and R. Outside the current palindrome, begin with the trivial center radius and expand normally.
- Mirror around L+R
- Boundary distance caps reuse
- Only expansions beyond R are new work
Terms, operations, and practical uses
Palindrome radii
- Odd radiusOdd radius is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Even radiusEven radius is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- CenterCenter is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Mirror reuse
- Rightmost palindromeRightmost palindrome is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Mirror centerMirror center is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Boundary clippingBoundary clipping is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Results
- Longest palindromeLongest palindrome is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Occurrence countOccurrence count is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Radius conventionRadius convention is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Manacher expands and mirrors palindrome radii
s="abacaba";n=len(s);d=[0]*n;l=0;r=-1
for i in range(n):
k=1 if i>r else min(d[l+r-i],r-i+1)
while i-k>=0 and i+k<n and s[i-k]==s[i+k]:k+=1
d[i]=k
if i+k-1>r:l,r=i-k+1,i+k-1
i=max(range(n),key=d.__getitem__);k=d[i]
print("Longest palindrome:",s[i-k+1:i+k])#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
string s="abacaba";
int n=s.size(),l=0,r=-1,best=0,center=0;
vector<int>d(n);
for(int i=0;i<n;i++) {
int k=i>r?1:min(d[l+r-i],r-i+1);
while(i-k>=0&&i+k<n&&s[i-k]==s[i+k]) k++;
d[i]=k;
if(k>best) best=k,center=i;
if(i+k-1>r) l=i-k+1,r=i+k-1;
}
cout << "Longest palindrome: " << s.substr(center-best+1,2*best-1) << '\n';
}class Main {
public static void main(String[] args) {
String s="abacaba";
int n=s.length(),l=0,r=-1,best=0,center=0;
int[] d=new int[n];
for(int i=0;i<n;i++) {
int k=i>r?1:Math.min(d[l+r-i],r-i+1);
while(i-k>=0&&i+k<n&&s.charAt(i-k)==s.charAt(i+k)) k++;
d[i]=k;
if(k>best) {
best=k;
center=i;
}
if(i+k-1>r) {
l=i-k+1;
r=i+k-1;
}
}
System.out.println("Longest palindrome: "+s.substring(center-best+1,center+best));
}
}Step through it
Running on abacaba
Linear-time proof
Each successful comparison beyond the current boundary increases R. Since R never decreases and crosses at most N positions, all boundary-extending comparisons total O(N). Mirror copies and failed comparisons contribute constant work per center.
The proof does not claim every center expands once; it claims repeated interior information is copied while genuinely new comparisons monotonically extend one global frontier.
- New comparisons extend R
- Interior radii are reused
- Total work is O(N)
Recovering the longest palindrome
For odd radius k at center i, length is 2k−1 and start is i−k+1. For even radius k, length is 2k and start is i−k. Track the best while building radii or scan afterward.
Ties need a policy such as earliest start. Empty input returns an empty answer; one character has odd radius one. The radius convention must match the formulas used for extraction.
- Odd length is 2k−1
- Even length is 2k
- Tie behavior should be deterministic
Testing the symmetry logic
Test even and odd answers, all-equal text, no palindrome longer than one, nested palindromes, repeated best answers, and boundary centers. Compare small random strings against center expansion.
Sentinel-based implementations must choose characters absent from input and prevent accidental equality with boundaries. Separate arrays avoid that risk and are often clearer for production Unicode text.
- Cross-check with center expansion
- Boundaries expose off-by-one errors
- Sentinels must not collide
Radius conventions in production code
Document whether an odd radius counts the center and whether an even radius is anchored between i−1 and i. Print the radius array beside extracted substrings in tests; most failures come from applying formulas from a different convention.
Manacher answers static palindrome queries after linear preprocessing, but it does not directly maintain radii under edits. Hashing can answer candidate palindrome equality dynamically with collision risk, while palindromic trees organize distinct palindromes. Select by the output required, not only the linear-time headline.
The algorithm returns compact information for every center, enabling palindrome-count totals by summing radii under the chosen convention. Listing every occurrence still takes output-sensitive quadratic time on strings such as aaaaa, so preprocessing complexity must not be confused with enumeration cost.
The rightmost known palindrome gives a certified symmetric region. If i lies inside it, the mirror radius is reusable only up to the current right boundary; any claimed characters beyond that boundary were never compared. Starting with the clipped radius preserves correctness, and only new comparisons extend the boundary. This is also the linear-time argument: successful expansions move the right boundary rightward at most n times. Test empty and one-character strings, even-only answers such as abba, tied longest answers, all-equal text, and Unicode assumptions. In languages indexing bytes, clarify whether the algorithm processes bytes, code points, or grapheme clusters.
- State the radius convention
- Test radii and extracted ranges together
- Dynamic text needs different structures