Palindromic Tree (Eertree)

A structure with one node per distinct palindromic substring, built online in $O(n)$. The key fact that makes it possible:

A string of length $n$ contains at most $n$ distinct palindromic substrings.

Why: each new character adds at most one new palindrome — the longest palindromic suffix of the new prefix. Any shorter palindromic suffix also occurred earlier (it is a suffix of the longest one, and by symmetry a prefix of it, so it appeared before).

Structure

Two roots: one of length $-1$ (imaginary, for odd palindromes) and one of length $0$ (for even). Each node stores:

• len — the palindrome’s length,
• link — the longest proper palindromic suffix of this palindrome,
• nxt[c] — the node for $c+\text{this palindrome}+c$,
• cnt — occurrence count (propagated at the end).

Construction

struct Eertree {
    static const int A = 26;
    struct Node { int len, link, cnt = 0; array<int,A> nxt; };
    vector<Node> t;
    string s;
    int suff;                                     // node of the longest palindromic suffix
 
    Eertree() {
        t.push_back({-1, 0, 0, {}}); t[0].nxt.fill(0);   // root -1
        t.push_back({ 0, 0, 0, {}}); t[1].nxt.fill(0);   // root 0
        t[1].link = 0;
        suff = 1;
    }
 
    int getLink(int v, int pos) {                 // longest palindromic suffix we can extend
        while (pos - t[v].len - 1 < 0 || s[pos - t[v].len - 1] != s[pos]) v = t[v].link;
        return v;
    }
 
    void add(char c) {
        s += c;
        int pos = s.size() - 1;
        int cur = getLink(suff, pos);
        if (!t[cur].nxt[c - 'a']) {               // a new palindrome
            int now = t.size(); t.push_back({});
            t[now].len = t[cur].len + 2;
            t[now].nxt.fill(0);
            t[now].link = t[getLink(t[cur].link, pos)].nxt[c - 'a'];
            if (t[now].len == 1) t[now].link = 1;
            t[cur].nxt[c - 'a'] = now;
        }
        suff = t[cur].nxt[c - 'a'];
        t[suff].cnt++;
    }
 
    void finalize() {                             // propagate counts down the link tree
        for (int i = t.size() - 1; i > 1; i--) t[t[i].link].cnt += t[i].cnt;
    }
};

$O(n\sigma )$ memory with array transitions; $O(n)$ time amortized, by the same argument as the prefix function — suff’s depth increases by at most 1 per character.

What it answers

Question	Method
Number of distinct palindromic substrings	t.size() - 2
Number of occurrences of each palindrome	cnt after finalize()
Total palindromic substrings with multiplicity	$\sum \mathrm{cnt}$
Longest palindromic substring	max len
Longest palindromic suffix of each prefix	suff after each add
Number of palindromes ending at each position	depth in the link tree
Minimum palindromic factorisation	series links, $O(n\log n)$
Count palindromic substrings of each length	group nodes by len

Series links — the $O(n\log n)$ factorisation

The palindromic suffixes of any prefix fall into $O(\log n)$ arithmetic progressions by length. Adding a serieslink (the previous palindrome with a different period) plus a per-series DP value lets you compute the minimum number of palindromes a string factors into, in $O(n\log n)$ — a result that is otherwise surprisingly hard.

// in addition to link:
// diff[v]   = len[v] - len[link[v]]
// slink[v]  = link[v] if diff[v] != diff[link[v]], else slink[link[v]]

This is the standard solution to “partition the string into the fewest palindromes”.

Eertree vs the alternatives

Task	Eertree	Manacher	Hashing
Longest palindromic substring	✔	✔ simplest	✔
Count all palindromic substrings	✔	✔	✔
Count distinct palindromes	✔ only this	✘	$O(n^2)$
Occurrences of each palindrome	✔	✘	✘
Palindromic factorisation	✔	✘	$O(n^2)$ DP
Online (append characters)	✔	✘	✔
Code length	~40 lines	~15 lines	~30 lines

Use Manacher for “longest” and “count with multiplicity”; use Eertree when distinctness, per-palindrome counts, or factorisation is involved.

Generalisations

• Bidirectional Eertree — supports appending at both ends, for problems about growing a string from the middle.
• Persistent Eertree — for offline tree problems where each root-to-node path is a string.
• Eertree on a tree — palindromes along root-to-vertex paths, built with a DFS and rollbacks.

See also: Palindromes · Manacher · Suffix Automaton