Manacher's Algorithm — Longest Palindromic Substring in O(n)

Manacher's Key Insight

Transform s to #a#b#a#b#a# to handle even/odd uniformly.

Maintain the rightmost palindrome [l, r] and its centre c. For each position i:

If i < r: use mirror 2*c - i as starting radius
Extend and update [l, r, c] if extended past r

Solutions

Python

def longestPalindrome(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0]*n
    c = r = 0
    for i in range(n):
        mirror = 2*c-i
        if i < r:
            p[i] = min(r-i, p[mirror])
        while i+p[i]+1 < n and i-p[i]-1 >= 0 and t[i+p[i]+1] == t[i-p[i]-1]:
            p[i] += 1
        if i+p[i] > r:
            c, r = i, i+p[i]
    max_len = max(p)
    centre = p.index(max_len)
    start = (centre-max_len)//2
    return s[start:start+max_len]

JavaScript

function longestPalindrome(s) {
    const t='#'+s.split('').join('#')+'#',n=t.length,p=new Array(n).fill(0);
    let c=0,r=0;
    for(let i=0;i<n;i++){
        if(i<r)p[i]=Math.min(r-i,p[2*c-i]);
        while(i+p[i]+1<n&&i-p[i]-1>=0&&t[i+p[i]+1]===t[i-p[i]-1])p[i]++;
        if(i+p[i]>r){c=i;r=i+p[i];}
    }
    const ml=Math.max(...p),ci=p.indexOf(ml),start=(ci-ml)/2;
    return s.slice(start,start+ml);
}

Java

public String longestPalindrome(String s) {
    String t="#"+String.join("#",s.split("")+"#");
    int n=t.length(); int[]p=new int[n]; int c=0,r=0;
    for(int i=0;i<n;i++){if(i<r)p[i]=Math.min(r-i,p[2*c-i]);while(i+p[i]+1<n&&i-p[i]-1>=0&&t.charAt(i+p[i]+1)==t.charAt(i-p[i]-1))p[i]++;if(i+p[i]>r){c=i;r=i+p[i];}}
    int ml=0,ci=0;for(int i=0;i<n;i++)if(p[i]>ml){ml=p[i];ci=i;}
    return s.substring((ci-ml)/2,(ci+ml)/2);
}

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string longestPalindrome(string s){
    string t="#"; for(char c:s){t+=c;t+='#';} int n=t.size();
    vector<int>p(n,0); int c=0,r=0;
    for(int i=0;i<n;i++){if(i<r)p[i]=min(r-i,p[2*c-i]);while(i+p[i]+1<n&&i-p[i]-1>=0&&t[i+p[i]+1]==t[i-p[i]-1])p[i]++;if(i+p[i]>r){c=i;r=i+p[i];}}
    int ml=*max_element(p.begin(),p.end()),ci=max_element(p.begin(),p.end())-p.begin();
    return s.substr((ci-ml)/2,ml);
}

C

/* C: same transformation + p[] array with c/r tracking */