Manacher's Algorithm

Manacher's algorithm finds the longest palindrome radius at every possible center in linear time. A palindrome reads the same forward and backward. Expanding independently around every center is simple but can take quadratic time on strings such as aaaaa. Manacher reuses symmetry inside a palindrome already discovered, then performs new comparisons only where the answer is not yet known. We compute separate arrays for odd-length and even-length palindromes, avoiding artificial separator characters and handling both parities explicitly.

Prerequisites: String indexing, center expansion, symmetry, inclusive intervals, and amortized analysis.

Build the idea

1. 1. Define the two radius conventions before coding. odd[i] is the number of characters from center i through one side, including the center. Its maximal interval is [i−odd[i]+1, i+odd[i]−1] with length 2·odd[i]−1. Every actual character has odd radius at least 1. even[i] counts pairs around the gap immediately before index i, between i−1 and i. Its interval is [i−even[i], i+even[i]−1] with length 2·even[i], and its radius may be zero. These formulas use inclusive palindrome endpoints, though the C++ substring function later takes start and length.
2. 2. Maintain the rightmost known palindrome. Process centers from left to right. Keep inclusive boundaries [l,r] of a palindrome whose right endpoint is as far right as any palindrome processed so far. If the new odd center i lies outside r, only its own character is initially guaranteed, so start radius k=1. If i lies inside [l,r], the reflected center j=l+r−i has already been processed. Reflection inside a palindrome makes the local character equalities around j usable around i, as long as they stay within the known boundaries.
3. 3. Clip the mirror information at the boundary. For an odd center inside the known palindrome, initialize k=min(odd[j], r−i+1). The mirrored radius can extend beyond the region whose symmetry is established; copying it without this minimum can claim nonexistent matches. If the mirrored palindrome ends strictly before the boundary, its answer is already exact at the new center. If it touches the boundary, the new palindrome might extend farther, so compare s[i−k] with s[i+k] and expand while valid. Afterward update [l,r] only when the new right endpoint increases.
4. 4. Adjust the geometry for even centers. For the gap before i, start with k=0 outside the known palindrome. Inside it, the mirrored gap index is j=l+r−i+1, one larger than the odd-center formula. Initialize k=min(even[j],r−i+1). The next comparison is between s[i−k−1] and s[i+k], because the center lies between characters. Once expansion finishes, the interval becomes [i−k,i+k−1]. Using the odd mirror formula in the even loop is an off-by-one error; deriving it from gap positions is safer than memorizing two nearly identical snippets.
5. 5. Check both parities on small strings. For abba, odd radii are [1,1,1,1]. The gap before index 2 lies between the two b characters: first b equals b, then a equals a, producing even[2]=2 and palindrome [0,3]. Other even radii are zero. For abacaba, odd[3]=4 gives the entire seven-character palindrome, while all even radii are zero. If i=5 lies inside that known whole-string palindrome, its odd mirror is 1; the mirror radius is reused only up to the current right boundary before any possible extension is examined.
6. 6. Prove linear time rather than relying on appearances. A copied radius already accounts for comparisons wholly inside the known palindrome. Further successful expansion comparisons reach beyond the current right endpoint and advance that endpoint. Across a whole odd pass, r can advance at most N times. Each center also contributes at most one failing expansion comparison, or stops at a string boundary. Thus each parity takes O(N) time despite containing a while loop inside a for loop. The even pass has the same amortized argument. This is why a string containing only one repeated character remains linear-time.
7. 7. Extract useful answers from the radii. Compare lengths 2·odd[i]−1 and 2·even[i] to find a longest palindromic substring. The example chooses the earliest start if several longest substrings tie. The total number of palindromic occurrences, counting equal text at different positions separately, is sum(odd)+sum(even): each smaller radius around a center contributes exactly one additional palindrome. This count can be quadratic, so store it in long long. Radii themselves occupy only O(N) memory, while explicitly listing every palindrome could require Θ(N²) output.
8. 8. Keep the input and equality model clear. getline reads spaces and accepts an empty first line. For the empty string, both radius arrays are empty, the longest length and start are 0, the printed substring is blank, and the palindrome count is 0. Comparisons operate on bytes, so multibyte Unicode text needs decoding into code points before using the same algorithm. Manacher answers exact palindrome questions; unlike rolling hashes, it has no collision issue. It does not directly solve longest common subsequence or require that the palindrome begin at index zero.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    int n=(int)s.size();
    vector<int>odd(n),even(n);
    int l=0,r=-1;
    for(int i=0;i<n;i++){
        // Reflect an already known odd palindrome, clipped to [l,r].
        int k=(i>r)?1:min(odd[l+r-i],r-i+1);
        while(i-k>=0&&i+k<n&&s[i-k]==s[i+k]){
            ++k;
        }
        odd[i]=k;
        if(i+k-1>r){
            l=i-k+1;
            r=i+k-1;
        }
    }
    l=0;
    r=-1;
    for(int i=0;i<n;i++){
        // Even centers lie before i; the mirror therefore has an extra +1.
        int k=(i>r)?0:min(even[l+r-i+1],r-i+1);
        while(i-k-1>=0&&i+k<n&&s[i-k-1]==s[i+k]){
            ++k;
        }
        even[i]=k;
        if(i+k-1>r){
            l=i-k;
            r=i+k-1;
        }
    }
    int bestLength=0,bestStart=0;
    long long total=0;
    auto consider=[&](int start,int length){
        if(length>bestLength||(length==bestLength&&start<bestStart)){
            bestLength=length;
            bestStart=start;
        }
    };
    for(int i=0;i<n;i++){
        consider(i-odd[i]+1,2*odd[i]-1);
        consider(i-even[i],2*even[i]);
        // Every smaller radius defines one more distinct positional occurrence.
        total+=(long long)odd[i]+even[i];
    }
    cout<<"ODD";
    for(int x:odd){
        cout<<' '<<x;
    }
    cout<<"\nEVEN";
    for(int x:even){
        cout<<' '<<x;
    }
    cout<<"\nLONGEST "<<bestLength<<' '<<bestStart<<'\n';
    cout<<s.substr(bestStart,bestLength)<<'\n';
    cout<<"COUNT "<<total<<'\n';
}

Complexity analysis

O(N) total time and O(N) space for the two radius arrays. Each pass advances its right boundary at most N times and does at most one unsuccessful expansion per center. Finding the longest substring and total count is another O(N) scan. Enumerating all palindromic occurrences can take Θ(N²) time because the output itself can be that large.

Example input and output

One complete text line, possibly empty. Output ODD radii, EVEN radii, LONGEST length startIndex, the chosen substring, and COUNT totalOccurrences. Longest ties choose the earliest start.

Input

abba

Output

ODD 1 1 1 1
EVEN 0 0 2 0
LONGEST 4 0
abba
COUNT 6

Four single-character palindromes, bb, and abba give six occurrences. The only positive even radius is 2 at the gap before index 2.

Practical applications

Longest palindromic substring, counting palindromic occurrences, testing whether an interval is a palindrome from its center/radius, and palindrome-based string problems. Palindromic trees organize distinct palindrome values; Manacher organizes palindrome occurrences by center.

Check your understanding

Why must a reused mirror radius be clipped to the current right boundary?

Put it into practice

After preprocessing, answer whether any given interval [a,b) is a palindrome in O(1).