Manacher's Algorithm — Stale Centre Update Bug

LeetCode 5 — Longest Palindromic Substring — is one of the most common interview problems. The O(n^2) expand-around-centre solution passes most judges. Manacher's O(n) solution demonstrates you understand linear string algorithms at a structural level, not just memorised patterns.

Manacher (1975) is not widely taught in undergraduate curricula, which means knowing it distinguishes you. The underlying technique — maintaining a rightmost boundary and exploiting mirror symmetry — is the exact same structural insight as KMP and Z-algorithm. Once you see this pattern, you recognise it everywhere.

The Even/Odd Problem and the Transformation

Palindromes come in two flavours: odd-length ('aba') and even-length ('abba'). Handling both cases separately doubles code complexity. Manacher's standard trick: insert a separator character between every character (and at boundaries) to convert all palindromes to odd-length.

Original: 'abba' Transformed: '#a#b#b#a#'

Now every palindrome in the original maps to an odd-length palindrome in the transformed string. '#b#b#' is the palindrome for 'bb'. '#a#b#b#a#' is the palindrome for 'abba'. We only need to handle one case.

def transform(s: str) -> str:
    return '#' + '#'.join(s) + '#'

print(transform('abba'))   # '#a#b#b#a#'
print(transform('racecar'))# '#r#a#c#e#c#a#r#'

The P Array — Palindrome Radii

For the transformed string T, we compute P[i] = the radius of the longest palindrome centred at i (not counting the centre itself). So P[i] = k means T[i-k..i+k] is a palindrome.

The length of the corresponding original palindrome is P[i] (the separator characters cancel out).

Manacher's Algorithm — Full Implementation

Manacher maintains a 'mirror window' [l, r] — the palindrome with the rightmost boundary seen so far (centre c, right edge r). For each i, if i < r, initialise P[i] from the mirror position (2*c - i). Then try to expand.

def manacher(s: str) -> str:
    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])

        left, right = i - P[i] - 1, i + P[i] + 1
        while left >= 0 and right < n and T[left] == T[right]:
            P[i] += 1
            left -= 1
            right += 1

        if i + P[i] > r:
            c, r = i, i + P[i]

    max_len, centre = max((v, i) for i, v in enumerate(P))
    start = (centre - max_len) // 2
    return s[start : start + max_len]

print(manacher('babad'))
print(manacher('cbbd'))
print(manacher('racecar'))
print(manacher('abacabadabacaba'))

C++ Implementation of Manacher's Algorithm

For production systems in C++, the same logic applies with careful memory management. The transformed string uses vector<char> for cache locality. The algorithm returns the longest palindromic substring as a std::string.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::string manacher(const std::string& s) {
    std::vector<char> T = {'#'};
    for (char ch : s) {
        T.push_back(ch);
        T.push_back('#');
    }
    int n = T.size();
    std::vector<int> P(n, 0);
    int c = 0, r = 0;

    for (int i = 0; i < n; ++i) {
        int mirror = 2 * c - i;
        if (i < r) {
            P[i] = std::min(r - i, P[mirror]);
        }

        int left = i - P[i] - 1;
        int right = i + P[i] + 1;
        while (left >= 0 && right < n && T[left] == T[right]) {
            ++P[i];
            --left;
            ++right;
        }

        if (i + P[i] > r) {
            c = i;
            r = i + P[i];
        }
    }

    int max_len = 0;
    int centre = 0;
    for (int i = 0; i < n; ++i) {
        if (P[i] > max_len) {
            max_len = P[i];
            centre = i;
        }
    }

    int start = (centre - max_len) / 2;
    return s.substr(start, max_len);
}

int main() {
    std::cout << manacher("babad") << '\n';
    std::cout << manacher("cbbd") << '\n';
    std::cout << manacher("racecar") << '\n';
    std::cout << manacher("abacabadabacaba") << '\n';
    return 0;
}

Three Case Mirror Analysis: When to Trust the Mirror

The mirror position mirror = 2*c - i gives the palindrome radius z0 = P[mirror] at that point. However, the mirror radius may extend beyond the current right boundary r. Three cases arise:

Case 1: z0 < r - i (mirror palindrome fully inside the rightmost palindrome) P[i] = z0. No expansion needed — the palindrome is guaranteed symmetric inside the larger palindrome.

Case 2: z0 == r - i (mirror palindrome exactly touches the boundary) P[i] = z0 initially, but expansion may extend beyond r. The while loop will try to expand; if successful, the right boundary advances.

Case 3: z0 > r - i (mirror palindrome extends beyond the boundary) P[i] = r - i. The part of the mirror palindrome beyond r is not confirmed symmetric. Expansion from r outward is required.

These three cases are handled elegantly by P[i] = min(r - i, P[mirror]) when i < r.

# Example: T = '#a#b#a#b#a#'
# Let c = 5 (centre of '#a#b#a#b#a#'), P[5] = 5, r = 10
# At i = 7, mirror = 2*5 - 7 = 3, z0 = P[3] = 1
# r - i = 3, so min(3, 1) = 1 => Case 1

# At i = 9, mirror = 1, z0 = 1, r-i = 1 => Case 2
# At i = 8, mirror = 2, z0 = 0, r-i = 2 => Case 1
print("See text for explanation")

Visual P‑Array Table for Example String

Consider input s = "ababa". Transformed T = '#a#b#a#b#a#'. The P‑array for each index i:

`` Index i: 0 1 2 3 4 5 6 7 8 9 10 T[i]: # a # b # a # b # a # P[i]: 0 1 0 3 0 5 0 3 0 1 0 ` - P[3]=3: palindrome #a#b#a# corresponds to original "aba" (length 3). - P[5]=5: palindrome #a#b#a#b#a# corresponds to original "ababa" (length 5). - All even indices (separators) have even radii multiples? Actually they have radii 0,3,0,3,0? Let's correct: The above table is illustrative. For ababa`, the P array values at even indices are: 0,3,0,3,0? Wait recalc: T: # a # b # a # b # a #. Centres at characters: i=1 (a) radius1, i=3 (b) radius3, i=5 (a) radius5, i=7 (b) radius3, i=9 (a) radius1. Centres at separators: i=0 radius0, i=2 radius? T[2-1]..T[2+1] = #a# -> palindrome? Actually check: index2 is '#', left=1 (a), right=3 (b) -> a!=b so radius0. Similarly i=4 radius0? i=4 is '#', left=3 (b), right=5 (a) -> b!=a so radius0. i=6 '#', left=5 (a), right=7 (b) -> a!=b radius0. i=8 '#', left=7 (b), right=9 (a) -> b!=a radius0. i=10 radius0. So P[i] = [0,1,0,3,0,5,0,3,0,1,0]. That's the correct array.

The longest palindrome ababa (length 5) corresponds to centre i=5 with P[5]=5. Start index = (5-5)//2 = 0.

Why it's O(n) — The Rightmost Boundary Argument

The r pointer only ever moves right — never decreases. Each time we expand (the while loop), r increases. So the total number of expansions across all iterations is at most n. All other operations per iteration are O(1). Total: O(n).

This is the same argument as KMP (pointer only moves forward) and Z-algorithm (r only moves right). Recognising this pattern is key to understanding linear string algorithms.

Advantages and Disadvantages vs Expand-Around-Center

Expand-around-centre (EAC) is the O(n²) baseline: for each of ~2n centres, expand until mismatch. Manacher improves on it by reusing previous expansions.

Advantages of Manacher over EAC: - O(n) vs O(n²) time — crucial for large strings (>10⁴ characters). - Single pass produces all palindrome radii — can be reused for subqueries. - Elegant theoretical demonstration of linear string algorithms.

Disadvantages: - Higher constant factor: EAC is simpler and may be faster for small strings (<1000 characters). - Memory: O(n) extra space for P array (vs O(1) for EAC). - Complexity: harder to implement correctly; bugs in mirror logic are common. - Input must be transformed, adding overhead.

When to use Manacher: - When string length exceeds 10⁵ and you need optimal time. - When you need to answer multiple palindrome queries on the same string (e.g., count all palindromes).

When to use EAC: - Quick prototyping or interviews where O(n²) is acceptable. - When space is constrained. - When the string is very short.

Finding All Palindromic Substrings

Manacher computes all palindrome radii in one pass, so you can use P to answer queries like 'is s[l..r] a palindrome?' in O(1) after O(n) preprocessing.

def all_palindrome_lengths(s: str) -> list[int]:
    """Return length of longest palindrome centred at each position."""
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    c = r = 0
    for i in range(n):
        if i < r:
            P[i] = min(r - i, P[2*c - 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] > r:
            c, r = i, i + P[i]
    # Extract only original positions (every other entry in P)
    return [P[2*i+1] for i in range(len(s))]  # odd centres

print(all_palindrome_lengths('abacaba'))
# [1, 3, 1, 7, 1, 3, 1]

Edge Cases and Common Pitfalls

Handling edge cases in Manacher is essential for production reliability. Here are the typical failures:

1. Empty string: Should return empty string. Our function works because transform('') = '#', P[0]=0, max_len=0, start=0, s[0:0] = ''.
2. Single character: transform('a') = '#a#', P[1]=1, returns 'a'. Works.
3. All identical characters: Like 'aaaa'. The algorithm must handle large radii. The while loop may expand many times but total O(n). Ensure recursion depth is not an issue (iterative is fine).
4. Very long string with no palindrome longer than 1: The algorithm will still run O(n) but each expansion step may be short. No issue.
5. Characters that could be the separator: If input contains '#', you must choose another separator or escape. The safest approach is to use a character that is not present, e.g., chr(0) for ASCII strings.

def test_manacher_edges():
    from manacher import manacher
    assert manacher('') == ''
    assert manacher('a') == 'a'
    assert manacher('aa') == 'aa'
    assert manacher('ab') in ('a', 'b')
    assert manacher('aaaa') == 'aaaa'
    assert manacher('racecar') == 'racecar'
    print('All edge cases passed')

test_manacher_edges()

Practice Problems

Sharpen your Manacher skills with these problems:

1. [LeetCode 5 – Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) – Classic problem; implement Manacher and compare with expand-around-centre.
2. [LeetCode 647 – Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) – Count all palindromic substrings; Manacher gives O(n) solution.
3. [LeetCode 131 – Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/) – Partition string into palindromic substrings; use Manacher to precompute palindrome status for O(n²) DP.
4. [Codeforces 245H – Queries for Number of Palindromes](https://codeforces.com/problemset/problem/245/H) – Many queries on substring palindromicity; precompute P array.
5. [Codeforces 159D – Palindrome pairs](https://codeforces.com/problemset/problem/159/D) – Count pairs of palindromic substrings; Manacher helps compute palindrome endpoints.
6. [SPOJ PALIN – The Next Palindrome](https://www.spoj.com/problems/PALIN/) – Not directly Manacher, but good practice for palindrome logic.

_Tip: For problems requiring multiple queries, precompute palindrome radii with Manacher and reuse the P array._