Manacher and Palindromic Structures

Odd/even palindrome radii, linear-time longest palindromic substring, palindromic tree (Eertree) overview, palindrome partitioning, and subsequence versus substring distinction.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Inserting # between characters makes every palindrome odd-length in t, so one loop handles both cases. Mirroring d[l + r − i] inside the rightmost known palindrome means r only ever moves right: O(n) total. A subsequence palindrome (letters need not be contiguous) is a different problem — the longest one is an O(n²) DP (LCS of s and its reverse). The palindromic tree (Eertree) stores each distinct palindromic substring once — there are at most n of them.

#include <bits/stdc++.h>
using namespace std;

// d[i] on t = "#a#b#..." = radius of the longest palindrome centred at i; handles odd and even at once
string longestPalindrome(const string& s, long long& work) {
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = (int)t.size(); vector<int> d(n, 0);
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = i > r ? 1 : min(d[l + r - i], r - i + 1);          // mirror inside the known palindrome [l, r]
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) { ++k; ++work; }
        d[i] = k--;
        if (i + k > r) { l = i - k; r = i + k; }
    }
    int best = int(max_element(d.begin(), d.end()) - d.begin());
    int len = d[best] - 1, start = (best - len) / 2;
    return s.substr(start, len);
}
string brute(const string& s) {
    string best;
    for (size_t i = 0; i < s.size(); ++i) for (size_t j = i; j < s.size(); ++j) {
        string sub = s.substr(i, j - i + 1);
        if (sub.size() > best.size() && equal(sub.begin(), sub.end(), sub.rbegin())) best = sub;
    }
    return best;
}

int main() {
    long long w = 0;
    for (string s : {"babad", "cbbd", "forgeeksskeegfor", "a"}) cout << s 
…

babad -> bab
cbbd -> bb
forgeeksskeegfor -> geeksskeeg
a -> a
matches brute force on 500 random strings; on 100000 identical letters the expansion loop ran 199999 times (linear)

Quiz

? Why insert '#' between characters before running Manacher?
+ Every palindrome in the new string has odd length, so one centre loop handles both odd and even cases. :: "abba" becomes "#a#b#b#a#".
- To avoid out-of-bounds access only :: Not the main reason.
- To sort the string :: No.
- It is needed for Unicode :: Unrelated.

? Why is Manacher O(n)?
+ The right boundary r of the known palindrome only moves right; each expansion step advances it. :: The run ran the expansion loop about 2n times on 10⁵ equal letters.
- Palindromes are short :: They can be the whole string.
- It uses hashing :: No.
- It is O(n log n) :: It is linear.

? The longest palindromic subsequence of a string…
+ is a different problem, solved by O(n²) DP :: Letters need not be contiguous.
- equals the longest palindromic substring :: Not in general ("abca" has subsequence "aca").
- is found by Manacher :: Manacher handles substrings.
- is always the whole string :: No.