Manacher's Algorithm

Introduction

A palindrome is a string that reads the same forwards and backwards — "racecar", "abacaba", "aa". The problem: given a string of length n, find the length of the longest palindromic substring.

The naive approach checks every possible center (O(n)) and expands outward (O(n)), giving O(n²) total. For n = 10⁶ that is 10¹² operations — too slow. Manacher's algorithm solves this in O(n) time by reusing work already done: when we know a large palindrome exists, positions inside it already have known minimum radii via mirror symmetry.

This page covers every detail: the odd and even cases, the separator trick that unifies them, a 2n−1 virtual-array variant that avoids string transformation, and a step-by-step animation that shows every variable at every step.

Odd & Even Palindromes

A palindrome has a center. For odd-length palindromes the center is a single character; for even-length palindromes the center sits between two characters.

Odd — center at a character

ababa

01234

p[2] = 2 (radius covers 2 chars each side)

Even — center between two characters

ab|ba

01↑23

p[2] = 2 (2 matching pairs)

A naive implementation runs two separate passes — one for odd palindromes, one for even. Manacher's key insight is that both cases can be handled in a single pass by choosing the right representation.

The Separator Trick

Insert a special character (conventionally #) between every character and at both ends. The string "abba" (length 4) becomes "#a#b#b#a#" (length 9 = 2·4+1).

Original: abba

↓ insert # between every character

Transformed: #a#b#b#a#

Every palindrome in the transformed string has an odd length — the separators ensure this. The center of any palindrome either sits on a # (corresponding to an even-length palindrome in the original) or on a real character (odd-length original palindrome). One pass, one algorithm.

A radius p[i] in the transformed string maps back to the original: the palindrome length in the original string is exactly p[i] (the # characters cancel out).

Variable Reference

Every variable in the algorithm is shown live in the animation below — arrows point to positions, and the radius is drawn as a blueprint dimension line. Here is what each one means:

Variable	Meaning	Color in animation
`s`	The input string (or transformed string for separator/virtual variants)	—
`p[i]`	Palindrome radius centered at `i`: `p[i] = k` means `s[i-k..i+k]` is a palindrome	—
`i`	Current index being processed	orange
`center` (C)	Center of the rightmost palindrome found so far. Shown as a dashed vertical line.	purple
`right` (R)	Right boundary of the rightmost palindrome: `right = center + p[center]`	green
`mirror`	Mirror of `i` around `center`: `mirror = 2·center − i`. Its known radius provides a head start for `p[i]`.	purple (lighter)

The core insight: as long as i < right, we know p[i] ≥ min(p[mirror], right − i) — no expansion needed up to that minimum.

Step-by-Step Animation

Input string:

radii p[]

Execution trace — the highlighted line is what changed the variables this step

Step 1 / 1

Speed:

Implementations

Four tabs for algorithm variants, six language tabs inside each.

Single pass over the original string. Handles odd-length palindromes only. p[i] = radius (number of chars each side).

// p[i] = radius of longest odd palindrome centered at i.
vector<int> manacher_odd(const string& s) {
    int n = s.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = min(p[mirror], right - i);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
               s[i-p[i]-1] == s[i+p[i]+1]) p[i]++;
        if (i + p[i] > right) { center = i; right = i + p[i]; }
    }
    return p;
}

def manacher_odd(s: str) -> list[int]:
    """p[i] = radius of longest odd palindrome centered at i."""
    n = len(s)
    p = [0] * n
    center = right = 0
    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(p[mirror], right - i)
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and \
              s[i-p[i]-1] == s[i+p[i]+1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return p

public static int[] manacherOdd(String s) {
    int n = s.length();
    int[] p = new int[n];
    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = Math.min(p[mirror], right - i);
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n &&
               s.charAt(i-p[i]-1) == s.charAt(i+p[i]+1)) p[i]++;
        if (i + p[i] > right) { center = i; right = i + p[i]; }
    }
    return p;
}

func manacherOdd(s string) []int {
    n := len(s)
    p := make([]int, n)
    center, right := 0, 0
    for i := 0; i < n; i++ {
        mirror := 2*center - i
        if i < right {
            if p[mirror] < right-i { p[i] = p[mirror] } else { p[i] = right - i }
        }
        for i-p[i]-1 >= 0 && i+p[i]+1 < n && s[i-p[i]-1] == s[i+p[i]+1] { p[i]++ }
        if i+p[i] > right { center, right = i, i+p[i] }
    }
    return p
}

fn manacher_odd(s: &[u8]) -> Vec<usize> {
    let n = s.len();
    let mut p = vec![0usize; n];
    let (mut center, mut right) = (0usize, 0usize);
    for i in 0..n {
        if i < right { p[i] = p[2*center - i].min(right - i); }
        while p[i]+1 <= i && i+p[i]+1 < n && s[i-p[i]-1] == s[i+p[i]+1] { p[i]+=1; }
        if i+p[i] > right { center = i; right = i+p[i]; }
    }
    p
}

function manacherOdd(s) {
    const n = s.length;
    const p = new Array(n).fill(0);
    let center = 0, right = 0;
    for (let i = 0; i < n; i++) {
        const mirror = 2 * center - i;
        if (i < right) p[i] = Math.min(p[mirror], right - i);
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n && s[i-p[i]-1] === s[i+p[i]+1]) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

Handles even-length palindromes. p[i] = number of matching pairs in an even palindrome whose right half starts at i.

// p[i] = even-palindrome radius; center is between s[i-1] and s[i].
vector<int> manacher_even(const string& s) {
    int n = s.size();
    vector<int> p(n, 0);
    int center = 0, right = -1;
    for (int i = 0; i < n; i++) {
        int mirror = center + (right - i) + 1;
        int init = (i <= right && mirror >= 0) ? min(p[mirror], right-i+1) : 0;
        p[i] = init;
        while (i-p[i]-1 >= 0 && i+p[i] < n && s[i-p[i]-1] == s[i+p[i]]) p[i]++;
        if (p[i] > 0 && i+p[i]-1 > right) { center = i; right = i+p[i]-1; }
    }
    return p;
}

def manacher_even(s: str) -> list[int]:
    n = len(s)
    p = [0] * n
    center, right = 0, -1
    for i in range(n):
        mirror = center + (right - i) + 1
        init = min(p[mirror], right-i+1) if i <= right and 0 <= mirror < n else 0
        p[i] = init
        while i-p[i]-1 >= 0 and i+p[i] < n and s[i-p[i]-1] == s[i+p[i]]:
            p[i] += 1
        if p[i] > 0 and i+p[i]-1 > right:
            center, right = i, i+p[i]-1
    return p

public static int[] manacherEven(String s) {
    int n = s.length();
    int[] p = new int[n];
    int center = 0, right = -1;
    for (int i = 0; i < n; i++) {
        int mirror = center + (right - i) + 1;
        int init = (i <= right && mirror >= 0) ? Math.min(p[mirror], right-i+1) : 0;
        p[i] = init;
        while (i-p[i]-1 >= 0 && i+p[i] < n && s.charAt(i-p[i]-1) == s.charAt(i+p[i])) p[i]++;
        if (p[i] > 0 && i+p[i]-1 > right) { center = i; right = i+p[i]-1; }
    }
    return p;
}

func manacherEven(s string) []int {
    n := len(s)
    p := make([]int, n)
    center, right := 0, -1
    for i := 0; i < n; i++ {
        mirror := center + (right - i) + 1
        init := 0
        if i <= right && mirror >= 0 && mirror < n {
            if p[mirror] < right-i+1 { init = p[mirror] } else { init = right - i + 1 }
        }
        p[i] = init
        for i-p[i]-1 >= 0 && i+p[i] < n && s[i-p[i]-1] == s[i+p[i]] { p[i]++ }
        if p[i] > 0 && i+p[i]-1 > right { center, right = i, i+p[i]-1 }
    }
    return p
}

fn manacher_even(s: &[u8]) -> Vec<usize> {
    let n = s.len();
    let mut p = vec![0usize; n];
    let mut center = 0usize;
    let mut right: Option<usize> = None;
    for i in 0..n {
        let init = match right {
            Some(r) if i <= r => {
                let mirror = center + (r - i) + 1;
                p[mirror].min(r - i + 1)
            }
            _ => 0,
        };
        p[i] = init;
        while p[i]+1 <= i && i+p[i] < n && s[i-p[i]-1] == s[i+p[i]] { p[i]+=1; }
        if p[i] > 0 && right.map_or(true, |r| i+p[i]-1 > r) {
            center = i; right = Some(i+p[i]-1);
        }
    }
    p
}

function manacherEven(s) {
    const n = s.length;
    const p = new Array(n).fill(0);
    let center = 0, right = -1;
    for (let i = 0; i < n; i++) {
        const mirror = center + (right - i) + 1;
        const init = (i <= right && mirror >= 0) ? Math.min(p[mirror], right-i+1) : 0;
        p[i] = init;
        while (i-p[i]-1 >= 0 && i+p[i] < n && s[i-p[i]-1] === s[i+p[i]]) p[i]++;
        if (p[i] > 0 && i+p[i]-1 > right) { center = i; right = i+p[i]-1; }
    }
    return p;
}

Transform s → #s[0]#s[1]#…s[n-1]# (length 2n+1). Run the odd algorithm once. p[i] in the transformed string equals the original palindrome length.

vector<int> manacher_unified_sep(const string& s) {
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        if (i < right) p[i] = min(p[2*center-i], right-i);
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n && t[i-p[i]-1] == t[i+p[i]+1]) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

def manacher_unified_sep(s: str) -> list[int]:
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(n):
        if i < right: p[i] = min(p[2*center-i], right-i)
        while i-p[i]-1 >= 0 and i+p[i]+1 < n and t[i-p[i]-1] == t[i+p[i]+1]: p[i]+=1
        if i+p[i] > right: center, right = i, i+p[i]
    return p

public static int[] manacherUnifiedSep(String s) {
    StringBuilder sb = new StringBuilder("#");
    for (char c : s.toCharArray()) { sb.append(c); sb.append('#'); }
    String t = sb.toString();
    int n = t.length();
    int[] p = new int[n];
    int center = 0, right = 0;
    for (int i = 0; i < n; i++) {
        if (i < right) p[i] = Math.min(p[2*center-i], right-i);
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n && t.charAt(i-p[i]-1) == t.charAt(i+p[i]+1)) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

func manacherUnifiedSep(s string) []int {
    t := "#" + strings.Join(strings.Split(s, ""), "#") + "#"
    n := len(t)
    p := make([]int, n)
    center, right := 0, 0
    for i := 0; i < n; i++ {
        if i < right { if p[2*center-i] < right-i { p[i]=p[2*center-i] } else { p[i]=right-i } }
        for i-p[i]-1 >= 0 && i+p[i]+1 < n && t[i-p[i]-1] == t[i+p[i]+1] { p[i]++ }
        if i+p[i] > right { center, right = i, i+p[i] }
    }
    return p
}

fn manacher_unified_sep(s: &str) -> Vec<usize> {
    let t: Vec<u8> = std::iter::once(b'#')
        .chain(s.bytes().flat_map(|c| [c, b'#']))
        .collect();
    let n = t.len();
    let mut p = vec![0usize; n];
    let (mut center, mut right) = (0usize, 0usize);
    for i in 0..n {
        if i < right { p[i] = p[2*center-i].min(right-i); }
        while p[i]+1 <= i && i+p[i]+1 < n && t[i-p[i]-1] == t[i+p[i]+1] { p[i]+=1; }
        if i+p[i] > right { center = i; right = i+p[i]; }
    }
    p
}

function manacherUnifiedSep(s) {
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p = new Array(n).fill(0);
    let center = 0, right = 0;
    for (let i = 0; i < n; i++) {
        if (i < right) p[i] = Math.min(p[2*center-i], right-i);
        while (i-p[i]-1 >= 0 && i+p[i]+1 < n && t[i-p[i]-1] === t[i+p[i]+1]) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

No string transformation. A virtual 2n−1 array: even indices map to s[i/2], odd indices are gaps that always match. Handles both odd and even palindromes without modifying the string.

// Even index k: s[k/2]. Odd index k: gap (always matches).
vector<int> manacher_unified_virt(const string& s) {
    int n = s.size(), m = 2*n-1;
    vector<int> p(m, 0);
    int center = 0, right = 0;
    auto matches = [&](int a, int b) {
        if (a < 0 || b >= m) return false;
        if (a%2 == 1) return true; // gap
        return s[a/2] == s[b/2];
    };
    for (int i = 0; i < m; i++) {
        if (i < right) p[i] = min(p[2*center-i], right-i);
        while (matches(i-p[i]-1, i+p[i]+1)) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

def manacher_unified_virt(s: str) -> list[int]:
    n, m = len(s), 2*len(s)-1
    p = [0] * m
    center = right = 0
    def matches(a, b):
        if a < 0 or b >= m: return False
        if a % 2 == 1: return True  # gap
        return s[a//2] == s[b//2]
    for i in range(m):
        if i < right: p[i] = min(p[2*center-i], right-i)
        while matches(i-p[i]-1, i+p[i]+1): p[i]+=1
        if i+p[i] > right: center, right = i, i+p[i]
    return p

public static int[] manacherUnifiedVirt(String s) {
    int n = s.length(), m = 2*n-1;
    int[] p = new int[m];
    int center = 0, right = 0;
    for (int i = 0; i < m; i++) {
        if (i < right) p[i] = Math.min(p[2*center-i], right-i);
        while (true) {
            int a = i-p[i]-1, b = i+p[i]+1;
            if (a < 0 || b >= m) break;
            if (a%2 == 1) { p[i]++; continue; }
            if (s.charAt(a/2) != s.charAt(b/2)) break;
            p[i]++;
        }
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

func manacherUnifiedVirt(s string) []int {
    n, m := len(s), 2*len(s)-1
    p := make([]int, m)
    center, right := 0, 0
    matches := func(a, b int) bool {
        if a < 0 || b >= m { return false }
        if a%2 == 1 { return true }
        return s[a/2] == s[b/2]
    }
    for i := 0; i < m; i++ {
        if i < right { if p[2*center-i] < right-i { p[i]=p[2*center-i] } else { p[i]=right-i } }
        for matches(i-p[i]-1, i+p[i]+1) { p[i]++ }
        if i+p[i] > right { center, right = i, i+p[i] }
    }
    _ = n
    return p
}

fn manacher_unified_virt(s: &[u8]) -> Vec<usize> {
    let n = s.len();
    let m = 2*n-1;
    let mut p = vec![0usize; m];
    let (mut center, mut right) = (0usize, 0usize);
    let matches = |a: usize, b: usize| -> bool {
        if b >= m { return false; }
        if a%2 == 1 { return true; }
        s[a/2] == s[b/2]
    };
    for i in 0..m {
        if i < right { p[i] = p[2*center-i].min(right-i); }
        while p[i]+1 <= i && matches(i-p[i]-1, i+p[i]+1) { p[i]+=1; }
        if i+p[i] > right { center = i; right = i+p[i]; }
    }
    p
}

function manacherUnifiedVirt(s) {
    const n = s.length, m = 2*n-1;
    const p = new Array(m).fill(0);
    let center = 0, right = 0;
    const matches = (a, b) => {
        if (a < 0 || b >= m) return false;
        if (a%2 === 1) return true;
        return s[a>>1] === s[b>>1];
    };
    for (let i = 0; i < m; i++) {
        if (i < right) p[i] = Math.min(p[2*center-i], right-i);
        while (matches(i-p[i]-1, i+p[i]+1)) p[i]++;
        if (i+p[i] > right) { center = i; right = i+p[i]; }
    }
    return p;
}

Known Variants & Applications

Count all palindromic substrings

After running Manacher's, the total count of palindromic substrings is ∑ ⌈(p[i]+1)/2⌉ for the odd variant, or ∑ (p[i]+1) over the unified transformed string. Each radius value accounts for all palindromes sharing that center.

Longest palindromic substring

Track the index maxC that maximizes p[maxC]. The answer is s[maxC − p[maxC] .. maxC + p[maxC]]. For the unified variant, map back to the original string: start = (maxC − p[maxC]) / 2, length = p[maxC].

Compact loop variant (competitive programming)

Instead of spelling out three mirror sub-cases explicitly, many contest implementations use a single expression to set the initial radius, then immediately enter the expansion loop:

p[i] = (i < right) ? min(p[2*center - i], right - i) : 0;
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && s[i-p[i]-1] == s[i+p[i]+1])
    p[i]++;
if (i + p[i] > right) { center = i; right = i + p[i]; }

This is algorithmically identical to the three-case version — the min already handles all three cases. The difference is purely cosmetic.

Eertree (Palindrome Tree)

The Eertree is a different data structure (not a variant of Manacher's) that represents all distinct palindromic substrings in a trie-like structure. It can count distinct palindromes, find the palindromic factorization, and more. Manacher's is simpler and sufficient for most problems; the Eertree is used when you need to process palindromes incrementally or need richer palindrome structure.

Complexity

Time: O(n)

The key observation is that right is monotonically non-decreasing throughout the algorithm. Each iteration of the inner expansion loop increments right by 1. Since right ≤ n, the total number of expansion steps across all positions is bounded by n. All other work per position is O(1). Total: O(n).

Space: O(n)

The p[] array has one entry per character: O(n). The separator-trick variant allocates a transformed string of length 2n+1: still O(n). The 2n−1 virtual-array variant avoids the extra string allocation entirely; its p[] array has 2n−1 entries: O(n).