Manacher’s Algorithm

Manacher’s Algorithm finds the longest palindromic substring centered at every position in time complexity $O(n)$.

Problem

Find array $d$ where:

• $d_1[i]$ = count of odd-length palindromes with center at position $i$ (counting radius including center)
• $d_2[i]$ = count of even-length palindromes with center between positions $i-1$ and $i$

Concept

Similar to Z-function, uses previously computed data to speed up computation of next positions.

Uses rightmost palindrome found so far (center $c$, right boundary $r$)

Implementation

Odd-length Palindromes

vector<int> manacherOdd(const string& s) {
    int n = s.size();
    vector<int> d(n, 1);  // d[i] = radius of palindrome centered at i
    
    int l = 0, r = -1;  // current rightmost palindrome [l, r]
    
    for (int i = 0; i < n; i++) {
        int k = 1;
        if (i <= r) {
            // Mirror position: i' = l + (r - i)
            k = min(d[l + r - i], r - i + 1);
        }
        
        // Expand palindrome
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        
        d[i] = k;
        
        // Update rightmost palindrome
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }
    
    return d;
}

Even-length Palindromes

vector<int> manacherEven(const string& s) {
    int n = s.size();
    vector<int> d(n, 0);  // d[i] = radius of palindrome centered between i-1 and i
    
    int l = 0, r = -1;
    
    for (int i = 0; i < n; i++) {
        int k = 0;
        if (i <= r) {
            k = min(d[l + r - i + 1], r - i + 1);
        }
        
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        
        d[i] = k;
        
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }
    
    return d;
}

Combined Version (using separator)

Transform string with separator to handle both odd and even:

string transform(const string& s) {
    string t = "^";  // start sentinel
    for (char c : s) {
        t += "#";
        t += c;
    }
    t += "#$";  // end sentinel
    return t;
}

vector<int> manacher(const string& s) {
    string t = transform(s);
    int n = t.size();
    vector<int> p(n, 0);
    
    int c = 0, r = 0;  // center and right boundary
    
    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * c - i;
        
        if (i < r) {
            p[i] = min(r - i, p[mirror]);
        }
        
        // Expand
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }
        
        // Update center
        if (i + p[i] > r) {
            c = i;
            r = i + p[i];
        }
    }
    
    return p;
}

Example

String: "abacaba"

Transformed: "^#a#b#a#c#a#b#a#$"

Index:  0 1 2 3 4 5 6 7 8 9 ...
Char:   ^ # a # b # a # c # ...
p[i]:   0 0 1 0 3 0 1 0 7 0 ...

$p[8] = 7$ means palindrome "abacaba" has radius 7 (in transformed string)

Applications

1. Longest Palindromic Substring

string longestPalindrome(const string& s) {
    vector<int> p = manacher(s);
    
    int maxLen = 0, center = 0;
    for (int i = 1; i < p.size() - 1; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            center = i;
        }
    }
    
    // Convert back to original string
    int start = (center - maxLen) / 2;
    return s.substr(start, maxLen);
}

2. Count Palindromic Substrings

long long countPalindromes(const string& s) {
    vector<int> d1 = manacherOdd(s);
    vector<int> d2 = manacherEven(s);
    
    long long count = 0;
    
    // Odd-length palindromes
    for (int x : d1) count += x;
    
    // Even-length palindromes
    for (int x : d2) count += x;
    
    return count;
}

3. Check if Substring is Palindrome

struct PalindromeChecker {
    vector<int> d1, d2;
    
    PalindromeChecker(const string& s) {
        d1 = manacherOdd(s);
        d2 = manacherEven(s);
    }
    
    // Check if s[l..r] is palindrome (0-indexed)
    bool isPalindrome(int l, int r) {
        int len = r - l + 1;
        int mid = (l + r) / 2;
        
        if (len % 2 == 1) {
            // Odd length: center at mid
            return d1[mid] >= (len + 1) / 2;
        } else {
            // Even length: center between mid and mid+1
            return d2[mid + 1] >= len / 2;
        }
    }
};

Complexity

Operation	Time	Space
Build arrays	$O(n)$	$O(n)$
Query substring	$O(1)$	-

Tips

1. Transformed string makes handling odd/even easier
2. Sentinel characters prevent boundary checks
3. Mirror property is the heart of the algorithm - use known palindromes to help compute
4. Actual length = p[i] in transformed string (when using separator)