Palindromes in O(N): Manacher's Algorithm & Eertree (Palindromic Automaton)

1. Manacher's Algorithm: Odd/Even Unification & Mirror Reflection

Palindromes come in two parities: odd-length (centered on a character, like $\texttt{"aba"}$) and even-length (centered between two characters, like $\texttt{"abba"}$). To avoid writing two separate passes, we transform $S[0..N-1]$ into $T[0..2N]$ of length $2N + 1$ by interleaving a separator $\texttt{'\#'}$: for $S = \texttt{"abba"}$, $T = \texttt{"\#a\#b\#b\#a\#"}$. Every odd or even palindrome in $S$ now maps bijectively to an odd-length palindrome in $T$, and the radius $p[i]$ (number of matching characters strictly to one side of $T[i]$) equals the exact length of the corresponding palindrome in $S$!

We maintain the active palindrome interval $[L, R] = [c - p[c],\; c + p[c]]$ with maximum right endpoint $R$. For index $i$ from $0$ to $2N$:

1. If $i < R$, let $i' = L + R - i$ be the reflection of $i$ across center $c$. Because $T[L..R]$ is a palindrome, the neighborhood around $i$ is the reverse of the neighborhood around $i'$ up to the boundary $R - i$. Thus we initialize: $$p[i] = \min(R - i,\; p[i'])$$
2. We then attempt to expand $p[i]$ greedily while $T[i - p[i] - 1] = T[i + p[i] + 1]$. Note that if $p[i'] < R - i$, the palindrome at $i'$ stopped strictly inside $[L, R]$ due to a mismatch $T[i' - p[i'] - 1] \neq T[i' + p[i'] + 1]$; by symmetry, the characters at $i \pm (p[i'] + 1)$ also mismatch, so the expansion loop terminates on its first check!
3. Whenever $i + p[i] > R$, we update $(L, R) \leftarrow (i - p[i],\; i + p[i])$. Since every successful character comparison increments $R$, and $R \le 2N$, Manacher's algorithm performs at most $2N + 1$ successful comparisons in total: $O(N)$ worst-case time.

2. Eertree (Palindromic Automaton): At Most $N$ Distinct Palindromes

How many distinct palindromic substrings can $S[0..N-1]$ contain? Consider appending $c = S[i]$ to prefix $S[0..i-1]$. Suppose two new palindromes $P_{\text{long}}$ and $P_{\text{short}}$ both end at index $i$ ($|P_{\text{short}}| < |P_{\text{long}}|$). Because $P_{\text{short}}$ is a suffix of $P_{\text{long}}$ and $P_{\text{long}}$ is a palindrome, $P_{\text{short}}$ must also appear as a prefix of $P_{\text{long}}$—meaning $P_{\text{short}}$ already occurred earlier inside $S[0..i-1]$! Thus appending $S[i]$ can create at most one new distinct palindrome (the longest palindromic suffix of $S[0..i]$), so a string of length $N$ has $\le N$ distinct non-empty palindromes.

An Eertree stores each distinct palindrome as a node $u$ with length $\text{len}[u]$, transition $\text{next}[u][c]$ representing the palindrome $c + S(u) + c$ of length $\text{len}[u] + 2$, and suffix link $\text{link}[u]$ pointing to the longest proper palindromic suffix of $S(u)$:

• Two Roots: Node $1$ is the imaginary odd root with $\text{len}[1] = -1$ (so wrapping $c$ around node $1$ gives $\text{len} = -1 + 2 = 1$, a single character $c$), and Node $2$ is the even empty root with $\text{len}[2] = 0$ and $\text{link}[2] = 1$ (so wrapping $c$ around node $2$ gives $cc$ of length $2$).
• Online Extension: From the longest palindromic suffix $u$ of $S[0..i-1]$, we follow $u \leftarrow \text{link}[u]$ until $S[i - 1 - \text{len}[u]] = S[i]$. Then $\text{next}[u][S[i]]$ is the longest palindromic suffix of $S[0..i]$.

3. Visual Trace: Manacher Mirror Reflection Across $[L, R]$

4. Production Implementation: Manacher + Online Eertree

#include <algorithm>
#include <array>
#include <string>
#include <string_view>
#include <vector>

// 1. Manacher's Algorithm with Sentinel Padding: returns p[i] on "^#s0#s1#...#$"
std::vector<int> manacher_radii(std::string_view s) {
    std::string t = "^#";
    t.reserve(2 * s.size() + 4);
    for (char c : s) {
        t.push_back(c);
        t.push_back('#');
    }
    t.push_back('$');

    const int m = static_cast<int>(t.size());
    std::vector<int> p(m, 0);
    int l = 1, r = 1;
    for (int i = 1; i < m - 1; ++i) {
        if (i < r) {
            p[i] = std::min(r - i, p[l + r - i]);
        }
        while (t[i - p[i] - 1] == t[i + p[i] + 1]) {
            ++p[i];
        }
        if (i + p[i] > r) {
            l = i - p[i];
            r = i + p[i];
        }
    }
    return p; // Max value in p equals length of longest palindromic substring of s
}

// 2. Eertree (Palindromic Automaton): counts distinct palindromes & total occurrences
struct Eertree {
    struct Node {
        std::array<int, 26> next{};
        int len = 0;
        int link = 0;
        long long occ = 0; // Occurrence count (accumulated bottom-up)
    };
    std::vector<Node> nodes;
    std::string s;
    int last = 2;

    Eertree() {
        nodes.resize(3);
        nodes[1].len = -1; nodes[1].link = 1; // Odd root
        nodes[2].len = 0;  nodes[2].link = 1; // Even root
    }

    int get_fail(int u, int pos) const {
        while (pos - 1 - nodes[u].len < 0 || s[pos - 1 - nodes[u].len] != s[pos]) {
            u = nodes[u].link;
        }
        return u;
    }

    void add_char(char ch) {
        int pos = static_cast<int>(s.size());
        s.push_back(ch);
        int c = ch - 'a';
        int cur = get_fail(last, pos);
        if (nodes[cur].next[c] == 0) {
            int now = static_cast<int>(nodes.size());
            nodes.emplace_back();
            nodes[now].len = nodes[cur].len + 2;
            if (nodes[now].len == 1) {
                nodes[now].link = 2; // Single char links to Even Root (len 0)
            } else {
                nodes[now].link = nodes[get_fail(nodes[cur].link, pos)].next[c];
            }
            nodes[cur].next[c] = now;
        }
        last = nodes[cur].next[c];
        nodes[last].occ++;
    }

    // Call after adding all characters to propagate occurrence counts up suffix links
    long long total_palindromic_substrings() {
        long long total = 0;
        for (int i = static_cast<int>(nodes.size()) - 1; i >= 3; --i) {
            nodes[nodes[i].link].occ += nodes[i].occ;
            total += nodes[i].occ;
        }
        return total;
    }
};