xi. Eertree and Palindromic Factorization

The eertree (palindromic tree) has one node per distinct palindromic substring, built online in $O(n)$: two roots (length $-1$ for odd, $0$ for even palindromes), and per node the length, the suffix link (longest proper palindromic suffix), transitions $v\to cvc$ and an occurrence count. It answers distinct-palindrome questions and, with series links, the minimum palindromic factorisation in $O(n\log n)$.

Question	Method
number of distinct palindromic substrings	nodes $-2$
occurrences of each palindrome; total with multiplicity	counts propagated up the suffix links; $\sum \mathrm{cnt}$
longest palindromic suffix of each prefix	the current node after each add
palindromes ending at each position	depth of that node in the link tree
palindromes of each length	group nodes by length
minimum palindromic factorisation of every prefix	series links, $O(n\log n)$

Task	eertree	Manacher	hashing
longest palindromic substring	yes	yes, simplest	yes
count all palindromic substrings	yes	yes	yes
count distinct palindromes; per-palindrome occurrences	only this	no	$O(n^2)$
palindromic factorisation	yes	no	$O(n^2)$ DP
online append	yes	no	yes

Generalisations: double-ended eertree (append at both ends), persistent eertree, eertree on a tree (DFS with rollback).

struct Eertree {                                            // lowercase
    struct Node { int len, link, cnt = 0, depth = 0; array<int, 26> nxt; };
    vector<Node> t; string s; int suff = 1;                 // node of the longest palindromic suffix
    vector<int> endCount;                                   // palindromes ending at each position
    Eertree() { t.push_back({-1, 0, 0, 0, {}}); t.push_back({0, 0, 0, 0, {}}); t[0].nxt.fill(0); t[1].nxt.fill(0); }
    int getLink(int v, int pos) const { while (pos - t[v].len - 1 < 0 || s[pos - t[v].len - 1] != s[pos]) v = t[v].link; return v; }
    void add(char ch) {
        s += ch; int pos = sz(s) - 1, c = ch - 'a', cur = getLink(suff, pos);
        if (!t[cur].nxt[c]) {
            int now = sz(t); t.push_back({t[cur].len + 2, 0, 0, 0, {}}); t[now].nxt.fill(0);
            t[now].link = t[now].len == 1 ? 1 : t[getLink(t[cur].link, pos)].nxt[c];
            t[now].depth = t[t[now].link].depth + 1;
            t[cur].nxt[c] = now;
        }
        suff = t[cur].nxt[c]; t[suff].cnt++; endCount.push_back(t[suff].depth);
    }
    void finalize() { for (int i = sz(t) - 1; i > 1; i--) t[t[i].link].cnt += t[i].cnt; }   // links point to earlier nodes
    int distinct() const { return sz(t) - 2; }
};
 
pair<vector<int>, vector<int>> minPalindromicFactorization(const string& s) {   // dp[i]: fewest palindromes for s[0, i); cut[i]: start of the last
    int n = sz(s);
    struct Node { int len, link, diff, slink; array<int, 26> next; };
    vector<Node> t; t.reserve(n + 2);
    t.push_back({-1, 0, 0, 0, {}}); t.push_back({0, 0, 0, 0, {}});
    int last = 1; const int INF = INT_MAX / 2;
    vector<int> dp(n + 1, INF), cut(n + 1, -1), series(n + 2, INF), seriesFrom(n + 2, -1); dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        auto fits = [&](int v) { return i - 1 - t[v].len >= 0 && s[i - 1 - t[v].len] == s[i]; };
        int cur = last; while (!fits(cur)) cur = t[cur].link;
        if (!t[cur].next[c]) {
            int w = sz(t); Node nd{t[cur].len + 2, 1, 0, 0, {}};
            if (nd.len > 1) { int x = t[cur].link; while (!fits(x)) x = t[x].link; nd.link = t[x].next[c]; }
            nd.diff = nd.len - t[nd.link].len;
            nd.slink = nd.diff == t[nd.link].diff ? t[nd.link].slink : nd.link;
            t.push_back(nd); t[cur].next[c] = w;
            if (sz(series) <= w) series.resize(w + 1, INF), seriesFrom.resize(w + 1, -1);
        }
        last = t[cur].next[c]; int pos = i + 1;
        for (int v = last; t[v].len > 0; v = t[v].slink) {
            int start = pos - (t[t[v].slink].len + t[v].diff);   // the shortest palindrome of the series
            series[v] = dp[start] + 1, seriesFrom[v] = start;
            if (t[v].diff == t[t[v].link].diff && series[t[v].link] < series[v]) series[v] = series[t[v].link], seriesFrom[v] = seriesFrom[t[v].link];
            if (series[v] < dp[pos]) dp[pos] = series[v], cut[pos] = seriesFrom[v];
        }
    }
    return {dp, cut};
}

Proof: at most $n$ distinct palindromes, linear construction, series links

At most one new palindrome per character. When $c$ is appended, a new palindromic substring must be a suffix of the new string; if $P$ is the longest palindromic suffix and $Q$ a shorter one, $Q$ is a suffix of $P$, hence (as $P$ is a palindrome) also a prefix of $P$, so $Q$ occurred earlier. So only $P$ can be new: at most $n$ distinct palindromes, and the tree has $\le n+2$ nodes. Construction. $P=cXc$ where $X$ is the longest palindromic suffix of the old string that is preceded by $c$; getLink walks the suffix-link chain from the previous longest palindromic suffix to find it. The suffix link of $P$ is $cYc$ for the longest proper palindromic suffix $Y$ of $X$ preceded by $c$ (or the single character, linking to the empty root). Linear time: the depth of suff in the link tree increases by at most one per character and each step of getLink decreases it, so the total is $O(n)$ (amortised like the prefix function). Counts: cnt of the longest palindromic suffix is incremented once per position; every palindrome ending at that position is on its link chain, so summing counts up the links (nodes are created after their links) gives occurrence counts, and the depth is the number of palindromes ending there.

Series. For palindromic suffixes $u$ of $v$ with $|v|\le 2|u|$, $|v|-|u|$ is a period of $v$; by the periodicity lemma the lengths of the palindromic suffixes form $O(\log n)$ arithmetic progressions (each new progression at least halves the length). diff is the step, slink jumps to the start of the next progression. For a series $\{u_1>u_2>\cdots >u_k\}$ with difference $d$, the set of starting positions $\{pos-|u_j|\}$ equals that of the series of link[v] at position $pos-d$, plus one new position (the shortest member), so the minimum $dp$ over the series is the stored value from $pos-d$ combined with the new start. Hence each position costs $O(\log n)$: $O(n\log n)$ total. Both verified against brute force ($O(n^2)$ palindromic DP and set counting).

Related notes

• Palindromes
• String Basics (periodicity lemma)
• Suffix Automaton