Manacher’s Algorithm

1. Overview

Manacher’s algorithm finds, in linear time O(N), the length of the longest palindromic substring centered at each position of a string. It works by transforming the input string to avoid even/odd cases, then using previously computed palindromic spans to “mirror” and skip redundant comparisons.

2. Algorithm Details

2.1 Preprocessing

Given original string S of length N, build a new string T = "^#" + S[0] + "#" + S[1] + "#…#"+S[N-1]+"#$". Here # are separators and sentinels ^ and $ guard bounds.

2.2 Radii Array

Create an integer array P of length len(T), where P[i] will hold the radius of the palindrome centered at i in T (excluding the center).

2.3 Main Loop

1. Maintain a center C and its right boundary R of the current rightmost palindrome.
2. For each i = 1…len(T)-2:
• Mirror position: mirror = 2*C - i.
• Initialize P[i] = min(R – i, P[mirror]) if i < R, else 0.
• Attempt to expand palindrome at i by comparing characters T[i + P[i] + 1] and T[i - P[i] - 1].
• If i + P[i] expands past R, update C = i and R = i + P[i].

2.4 Extracting Results

The longest palindromic substring in S has length maxLen = max(P[i]), and center index centerIndex = argmax(P[i]). Its start in S is (centerIndex - maxLen)/2.

3. Time & Memory Complexity

• Time: O(N) – each position is processed once, expansions amortize to linear.
• Memory: O(N) – storing transformed string T and array P.

4. Easy Problems

4.1 Longest Palindromic Substring (LeetCode #5)

Find the single longest palindromic substring in S.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n == 0) return "";
        // Transform
        string T = "^";
        for (char c : s) { T += "#"; T += c; }
        T += "#$";
        int N = T.size();
        vector P(N, 0);
        int C = 0, R = 0;
        for (int i = 1; i < N - 1; i++) {
            int mir = 2*C - i;
            if (i < R) P[i] = min(R - i, P[mir]);
            // 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]; }
        }
        // find max
        int maxLen = 0, centerIdx = 0;
        for (int i = 1; i < N - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIdx = i;
            }
        }
        int start = (centerIdx - maxLen) / 2;
        return s.substr(start, maxLen);
    }
};

int main() {
    Solution sol;
    string s = "babad";
    cout << sol.longestPalindrome(s) << endl;
    return 0;
}

4.2 Count Palindromic Substrings (LeetCode #647)

Count all palindromic substrings in S.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countSubstrings(string s) {
    int n = s.size(), ans = 0;
    string T = "^";
    for (char c : s) { T += "#"; T += c; }
    T += "#$";
    int N = T.size();
    vector P(N, 0);
    int C = 0, R = 0;
    for (int i = 1; i < N - 1; i++) {
        int mir = 2*C - i;
        if (i < R) P[i] = min(R - i, P[mir]);
        while (T[i + P[i] + 1] == T[i - P[i] - 1]) P[i]++;
        if (i + P[i] > R) { C = i; R = i + P[i]; }
        // each center contributes ceil(P[i]/2) palindromes in S
        ans += (P[i] + 1) / 2;
    }
    return ans;
}

int main() {
    cout << countSubstrings("aaa") << endl;  // Output: 6
    return 0;
}

5. Intermediate Problems

5.1 Shortest Palindrome (LeetCode #214)

Prepend the minimum characters to make S a palindrome. Compute the longest palindromic prefix via Manacher, then append the reverse of the remaining suffix.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string shortestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";
    // Build T = s + "#" + rev(s)
    string rev = s; reverse(rev.begin(), rev.end());
    string T = s + "#" + rev;
    int N = T.size();
    vector P(N, 0);
    int C = 0, R = 0;
    int maxPref = 0;
    for (int i = 0; i < N; i++) {
        int mir = 2*C - i;
        if (i < R) P[i] = min(R - i, P[mir]);
        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]; }
        // if palindrome reaches start of T, update longest prefix
        if (i - P[i] == 0) maxPref = max(maxPref, P[i]);
    }
    string suffix = s.substr(maxPref);
    reverse(suffix.begin(), suffix.end());
    return suffix + s;
}

int main() {
    cout << shortestPalindrome("aacecaaa") << endl;  // aaacecaaa
    return 0;
}

5.2 Longest Palindromic Substring in a Circular String

On a circular string, substrings can wrap around. Duplicate S to S+S, run Manacher, but only consider centers whose palindrome spans fewer than N characters.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int longestCircularPalindrome(string s) {
    int n = s.size();
    string ss = s + s;
    // transform
    string T = "^";
    for (char c : ss) { T += "#"; T += c; }
    T += "#$";
    int N = T.size();
    vector P(N, 0);
    int C = 0, R = 0, best = 0;
    for (int i = 1; i < N - 1; i++) {
        int mir = 2*C - i;
        if (i < R) P[i] = min(R - i, P[mir]);
        while (T[i + P[i] + 1] == T[i - P[i] - 1]) P[i]++;
        if (i + P[i] > R) { C = i; R = i + P[i]; }
        int len = P[i];
        // center in ss corresponds to index (i-1)/2
        int center = (i - 1) / 2;
        // ensure palindrome lies within any length-n window
        if (len > best && len <= n) best = len;
    }
    return best;
}

int main() {
    cout << longestCircularPalindrome("aba") << endl;  // 3
    return 0;
}

6. Hard Problem

6.1 Count Distinct Palindromic Substrings

Count how many distinct palindromic substrings appear in S. Use Manacher to enumerate all palindrome centers, extract each palindrome, and insert into a hash set.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

int countDistinctPalindromes(const string& s) {
    int n = s.size();
    string T = "^";
    for (char c : s) { T += "#"; T += c; }
    T += "#$";
    int N = T.size();
    vector P(N, 0);
    int C = 0, R = 0;
    unordered_set seen;
    for (int i = 1; i < N - 1; i++) {
        int mir = 2*C - i;
        if (i < R) P[i] = min(R - i, P[mir]);
        while (T[i + P[i] + 1] == T[i - P[i] - 1]) P[i]++;
        if (i + P[i] > R) { C = i; R = i + P[i]; }
        // extract palindromes centered at i
        for (int L = 1; L <= P[i]; L++) {
            if ((T[i-L] != '#') && (T[i+L] != '#')) {
                int start = (i - L - 1) / 2;
                int len = L;
                seen.insert(s.substr(start, len));
            }
        }
    }
    return seen.size();
}

int main() {
    cout << countDistinctPalindromes("ababa") << endl;  // Output: 3 ("a","b","aba","bab","ababa")
    return 0;
}