Chapter 109

Home

Manacher's Algorithm for Palindromes

Finding the longest palindromic substring naively is O(N²). Manacher's algorithm does it in O(N) by exploiting palindrome symmetry — mirroring already-computed radii across a centre.

Manacher's Algorithm

C++ — Manacher (odd + even)

vector manacher(string s) {
    // Insert separators: "abc" → "#a#b#c#"
    string t = "#";
    for (char c : s) { t += c; t += '#'; }

    int n = t.size();
    vector 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(right - i, p[mirror]);

        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];
        }
    }
    // p[i] = palindrome radius at position i in transformed string
    // Original palindrome length = p[i]
    // Longest palindrome = max(p)
    return p;
}

// O(N) — each character is compared at most once.

Key Takeaways