🗂️Data StructureAdvanced

Palindromic Tree (Eertree)

Key Points

  • •
    A Palindromic Tree (Eertree) stores every distinct palindromic substring of a string as a node and can be built online in linear time.
  • •
    Each node represents one unique palindrome, edges add the same character to both ends, and suffix links jump to the longest proper palindromic suffix.
  • •
    Two special roots of length -1 and 0 make all extensions uniform, handling odd and even palindromes elegantly.
  • •
    With simple bookkeeping, you can compute the number of distinct palindromes, total palindrome occurrences, and the longest palindromic substring.
  • •
    Construction is O(n) expected with hash maps or O(n ) with ordered maps, and memory is O(n).
  • •
    Eertree enables advanced DP like minimum palindromic partition in O(n) time using series links.
  • •
    It works online: after each new character, answers (like current longest palindrome) update immediately.
  • •
    Compared to Manacher’s algorithm, Eertree gives all distinct palindromes and their counts, not just the longest one.

Prerequisites

  • →String indexing and substrings — Understanding how substrings and indices work is essential for defining palindromes and implementing extensions.
  • →Basic graph/tree structures — Nodes, edges, and links are used throughout the Eertree, though it is not a pure tree.
  • →Hash maps vs arrays — Choosing the right transition structure affects time and memory complexity.
  • →Amortized analysis — Explains why suffix-link traversals lead to O(n) total time.
  • →Dynamic programming basics — Needed to apply Eertree to tasks like minimum palindromic partition.
  • →Manacher’s algorithm (optional) — Useful for contrast; shows what Eertree provides beyond longest-palindrome queries.
  • →Suffix automaton (optional) — For comparison with general substring structures and understanding specialization.
  • →C++ STL containers — std::unordered_map, std::map, and vector are heavily used in implementations.

Detailed Explanation

Tap terms for definitions

01Overview

A Palindromic Tree (often called an Eertree) is a compact data structure that stores all distinct palindromic substrings of a given string. Each node corresponds to exactly one palindrome, and edges are labeled by a single character indicating that the palindrome at the child node is formed by adding this character to both ends of the parent palindrome. The structure also keeps a suffix link from each node to the node representing its longest proper palindromic suffix. Two special roots are used: one of length −1 and one of length 0. This clever setup allows uniform handling of both odd and even length palindromes and ensures a simple, efficient online construction algorithm.

02Intuition & Analogies

Imagine nesting dolls or layers of mirrors. A palindrome is like a perfectly symmetric ornament: if you place a mirror at its center, the left and right halves match. When you read a string from left to right, you want to know which symmetric ornaments end at the current position. If you try to grow a palindrome by adding the same letter on both sides, sometimes it works (you extend the symmetry), and sometimes you need to “step down” to a smaller inner ornament before trying again. The suffix link is exactly this step-down: it takes you to the longest inner palindrome that might still be extendable. Edges labeled by characters are like trying a new color frame around an ornament—if both sides match this color, you’ve created a bigger symmetric ornament (a longer palindrome). The two special roots (length −1 and 0) act like base stands: one for odd palindromes with a clear center and one for even palindromes with a mirrored center. Because every failure to extend moves you to a smaller inner ornament, you never waste too much time—overall, you make steady progress, touching each character a constant number of times on average. By the time you’re done, each distinct ornament (palindrome) has its own node, and you’ve also recorded how often each appears in the full string by aggregating counts along the step-down (suffix) links.

03Formal Definition

Let S be a string of length n over an alphabet . The palindromic tree T is a directed structure with two distinguished roots and , storing: (1) For every distinct palindromic substring P of S, a node v with length (v) = . (2) For any node v and character c , if cPc is a palindrome in S, then an edge v u exists with (u) = (v) + 2 and string(u) = c string(v) c. (3) A suffix link (v) pointing to the node representing the longest proper palindromic suffix of string(v). The roots are: () = -1 with () = , and () = 0 with () = . Additionally, each node stores occurrence data: a counter (v) equals the number of occurrences of string(v) as a substring in S (after propagating counts along suffix links). Online construction maintains a pointer last to the node representing the longest palindromic suffix of the processed prefix; adding a new character extends from last via suffix links until a valid extension is found or a root is reached; if the resulting extended palindrome is new, a new node and transitions are added, and its suffix link is computed similarly by extending the suffix link of the parent.

04When to Use

Use an Eertree when you need full, online access to the set of all distinct palindromic substrings: for example, counting the distinct palindromes, finding the longest palindrome, or computing how many times each palindrome occurs. It’s particularly effective in competitive programming problems asking for palindrome statistics over the entire string, answering queries for each prefix, or performing dynamic updates by appending characters. Eertree-based dynamic programming can solve advanced tasks such as minimum palindromic partitioning in O(n) time with series links—ideal for high-difficulty problems. Compared to Manacher’s algorithm (which finds longest palindromes centered at each position), an Eertree retains structure and counts for all distinct palindromes, enabling more complex analyses. Compared to suffix automata/arrays, the Eertree is specialized: it sacrifices general substring operations but excels specifically on palindromes, often yielding simpler O(n) constructions and smaller memory for palindrome-centric tasks. If the alphabet is small and fixed (e.g., lowercase letters), you can use array transitions for speed; for larger alphabets (Unicode, arbitrary bytes), use hash maps or ordered maps with a slight time trade-off.

⚠️Common Mistakes

  • Forgetting to propagate occurrence counts up the suffix links leads to incorrect totals of palindrome occurrences. After building, you must aggregate counts from longer palindromes to their suffix-link parents in decreasing order of length.
  • Not initializing the two roots correctly (length −1 and 0) causes off-by-one and extension failures. Ensure R_{0}.link = R_{-1} and R_{-1}.link = R_{-1}.
  • Mixing 0-based and 1-based indices while computing extensions or DP indices often breaks correctness. Choose a convention and stick to it throughout add-character and DP steps.
  • Using std::map for transitions without realizing the time impact can make builds O(n \log \Sigma) instead of near O(n). Prefer arrays for small alphabets or unordered_map for expected O(1).
  • Storing transitions as a full array for very large alphabets can blow memory. Use sparse maps for large \Sigma.
  • When concatenating multiple strings, failing to use a separator character not appearing elsewhere leads to cross-string palindromes that should not exist.
  • In palindromic partition DP with series links, omitting the diff/seriesLink optimization results in O(n^2) time. Also, computing the candidate dp index incorrectly (off-by-one around len[seriesLink] + diff) is a common bug.
  • Forgetting to reset the last pointer when starting from an empty structure or when building for a new string can produce incorrect links and counts.

Key Formulas

Distinct Palindromes Count

Explanation: The number of distinct palindromic substrings D equals the number of nodes V in the Eertree minus the two special roots. Subtracting roots removes the artificial nodes of lengths −1 and 0.

Total Palindromic Substring Occurrences

Explanation: Summing occurrence counts over all non-root nodes gives the total number of palindromic substrings (counted with multiplicity) in the string. Occurrence counts must be propagated along suffix links from longer to shorter palindromes.

Construction Time

Explanation: Each character is processed once, and each failure to extend moves along suffix links, which amortizes to constant steps. Using unordere yields expected O(1) transition lookups; ordered maps add a factor.

Node Bound

Explanation: Each time you create a node, you discover a new distinct palindrome that ends at the current position. At most one new palindrome appears per position; plus the two roots, this bounds the number of nodes by n + 2.

diff Definition

Explanation: The diff value measures how much longer a palindrome is than its suffix-link target. Equal diffs across consecutive links enable grouping palindromes for DP acceleration.

Series Link

Explanation: Series links skip chains of suffix links with equal diff, forming groups that allow O(1) amortized transitions for certain DP tasks, like minimum palindromic partition.

Min Palindromic Partition (basic)

Explanation: The minimum number of palindromic substrings covering the prefix of length i equals one plus the minimum over all palindromes ending at i. Naively this is O(), but with series links it becomes O(n).

Partition DP via Series Links

Explanation: This recurrence reduces the candidate states to O(1) per series group when computing dp[i]. It enables O(n) minimum palindromic partition computation during Eertree construction.

Space Complexity

Explanation: The number of nodes and edges is linear in the string length. Each new node and its suffix link/transition is created at most once.

Complexity Analysis

Let n be the string length. The Eertree has at most n + 2 nodes, because at most one new distinct palindrome is created per position (the longest new palindrome ending at that position). For each added character, we attempt to extend from the node ‘last’ (the longest palindromic suffix of the processed prefix). If extension fails, we follow suffix links, strictly decreasing the palindrome length until extension succeeds or a root is reached. Over the entire build, the number of failed extensions is O(n) amortized, since each failure moves to a node with smaller length and each node cannot be the source of many consecutive failures. Thus, total pointer moves (successes plus failures) is O(n). Transition lookups depend on the transition dictionary: using an unordere yields expected O(1) per lookup (overall expected O(n) time), std::map yields O(log Σ) per lookup (overall O(n log Σ)), and fixed-size arrays (for small alphabets) yield O(1) worst-case per lookup with O(Σ) memory per node. Memory usage is O(n) nodes and O(n) edges (one creation transition per node plus one suffix link per node), so O(n) total. After construction, propagating occurrence counts along suffix links in decreasing order of palindrome length is O(n). Advanced DP using series links maintains O(1) amortized updates per series group per position, giving O(n) total time and O(n) additional memory for dp and auxiliary arrays. In summary: time O(n) expected (or O(n log Σ) with ordered maps), space O(n).

Code Examples

Core Eertree with generic alphabet (unordered_map), listing distinct palindromes and occurrences
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Eertree {
5    struct Node {
6        // Sparse transitions: character -> node index
7        unordered_map<char,int> next;
8        int link = 0;      // suffix link
9        int len = 0;       // palindrome length
10        long long occ = 0; // occurrence count (raw, then aggregated)
11        int firstPos = -1; // ending position of first occurrence
12    };
13
14    vector<Node> t; // nodes
15    string s;       // processed string
16    int last;       // node of the longest palindromic suffix of s
17
18    Eertree() { init(); }
19
20    void init() {
21        t.clear(); s.clear();
22        t.push_back(Node());               // 0: root with len = -1
23        t.push_back(Node());               // 1: root with len = 0
24        t[0].len = -1; t[0].link = 0;
25        t[1].len = 0;  t[1].link = 0;      // often set to 0
26        last = 1;                          // longest pal suffix of empty string is 0-length root
27    }
28
29    // Move via suffix links until we can extend by character c at position pos
30    int get_suff_link(int v, int pos, char c) {
31        while (true) {
32            int L = t[v].len;
33            if (pos - 1 - L >= 0 && s[pos - 1 - L] == c) return v;
34            v = t[v].link;
35        }
36    }
37
38    // Add character c at the end; returns id of the node for the LPS after insertion
39    int add_char(char c) {
40        int pos = (int)s.size();
41        s.push_back(c);
42
43        int cur = get_suff_link(last, pos, c);
44        if (t[cur].next.count(c)) {
45            // Palindrome already exists
46            last = t[cur].next[c];
47            t[last].occ++;
48            return last;
49        }
50
51        // Create new node
52        Node nn;
53        nn.len = t[cur].len + 2;
54        nn.occ = 1; // at least this occurrence
55        nn.firstPos = pos; // this palindrome ends at pos
56        t.push_back(nn);
57        int newId = (int)t.size() - 1;
58        t[cur].next[c] = newId;
59
60        if (nn.len == 1) {
61            // Single char palindrome: suffix link to empty root
62            t[newId].link = 1;
63            last = newId;
64            return last;
65        }
66
67        // Compute suffix link for the new node
68        int linkCand = t[cur].link;
69        linkCand = get_suff_link(linkCand, pos, c);
70        t[newId].link = t[linkCand].next[c];
71        last = newId;
72        return last;
73    }
74
75    // Propagate occurrence counts along suffix links (from longer to shorter)
76    void propagate_counts() {
77        vector<int> order(t.size());
78        iota(order.begin(), order.end(), 0);
79        sort(order.begin(), order.end(), [&](int a, int b){ return t[a].len < t[b].len; });
80        for (int i = (int)order.size() - 1; i >= 0; --i) {
81            int v = order[i];
82            if (v <= 1) continue; // skip roots
83            t[t[v].link].occ += t[v].occ;
84        }
85    }
86
87    int distinct_palindromes() const { return (int)t.size() - 2; }
88
89    string node_string(int v) const {
90        int L = t[v].len;
91        int end = t[v].firstPos;
92        int start = end - L + 1;
93        return s.substr(start, L);
94    }
95};
96
97int main() {
98    ios::sync_with_stdio(false);
99    cin.tie(nullptr);
100
101    string S; cin >> S;
102    Eertree et;
103    for (char c : S) et.add_char(c);
104    et.propagate_counts();
105
106    cout << "Distinct palindromes: " << et.distinct_palindromes() << "\n";
107
108    // Find the longest palindrome and list all palindromes with occurrence counts
109    int best = -1, bestId = -1;
110    for (int v = 2; v < (int)et.t.size(); ++v) {
111        if (et.t[v].len > best) { best = et.t[v].len; bestId = v; }
112    }
113    cout << "Longest palindrome length: " << best << "\n";
114
115    // Print palindromes (could be many). Limit for large strings.
116    int printed = 0, LIMIT = 50; // avoid flooding
117    for (int v = 2; v < (int)et.t.size() && printed < LIMIT; ++v) {
118        cout << et.node_string(v) << " : occ=" << et.t[v].occ << "\n";
119        printed++;
120    }
121    if ((int)et.t.size() - 2 > LIMIT) cout << "... (truncated)\n";
122    return 0;
123}
124

This implementation builds an Eertree online using unordered_map transitions (generic alphabet). The add_char method either reuses an existing palindrome or creates a new node, sets its suffix link, and updates last. After processing the string, propagate_counts aggregates occurrences along suffix links so each node.occ equals the total number of times that palindrome appears. The demo prints the number of distinct palindromes, the length of the longest palindrome, and a sample of palindromes with counts.

Time: Expected O(n) build with unordered_map (O(n log Σ) if std::map is used). Propagation is O(n).Space: O(n) nodes and edges; unordered_map overhead is proportional to the number of realized transitions (O(n)).
Lowercase-optimized Eertree (array transitions), computing total occurrences and LPS
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Eertree {
5    struct Node {
6        int next[26];
7        int link, len;
8        long long occ;
9        int firstPos;
10        Node() : link(0), len(0), occ(0), firstPos(-1) { fill(begin(next), end(next), -1); }
11    };
12
13    vector<Node> t;
14    string s;
15    int last;
16
17    Eertree() { init(); }
18
19    void init() {
20        t.clear(); s.clear();
21        t.push_back(Node()); // 0: len=-1
22        t.push_back(Node()); // 1: len=0
23        t[0].len = -1; t[0].link = 0;
24        t[1].len = 0;  t[1].link = 0;
25        last = 1;
26    }
27
28    int get_suff_link(int v, int pos, char c) {
29        while (true) {
30            int L = t[v].len;
31            if (pos - 1 - L >= 0 && s[pos - 1 - L] == c) return v;
32            v = t[v].link;
33        }
34    }
35
36    int add_char(char c) {
37        int pos = (int)s.size();
38        s.push_back(c);
39        int ci = c - 'a';
40        int cur = get_suff_link(last, pos, c);
41        if (t[cur].next[ci] != -1) {
42            last = t[cur].next[ci];
43            t[last].occ++;
44            return last;
45        }
46        Node nn;
47        nn.len = t[cur].len + 2;
48        nn.occ = 1;
49        nn.firstPos = pos;
50        t.push_back(nn);
51        int newId = (int)t.size() - 1;
52        t[cur].next[ci] = newId;
53        if (nn.len == 1) { t[newId].link = 1; last = newId; return last; }
54        int linkCand = t[cur].link;
55        linkCand = get_suff_link(linkCand, pos, c);
56        t[newId].link = t[linkCand].next[ci];
57        last = newId;
58        return last;
59    }
60
61    void propagate_counts() {
62        vector<int> order(t.size()); iota(order.begin(), order.end(), 0);
63        sort(order.begin(), order.end(), [&](int a, int b){ return t[a].len < t[b].len; });
64        for (int i = (int)order.size() - 1; i >= 0; --i) {
65            int v = order[i]; if (v <= 1) continue; t[t[v].link].occ += t[v].occ;
66        }
67    }
68
69    int distinct() const { return (int)t.size() - 2; }
70};
71
72int main(){
73    ios::sync_with_stdio(false);
74    cin.tie(nullptr);
75
76    string S; cin >> S;
77    Eertree et;
78    int bestLen = 0; string bestStr;
79    for (char c : S) {
80        int v = et.add_char(c);
81        if (et.t[v].len > bestLen) {
82            bestLen = et.t[v].len;
83            int end = et.t[v].firstPos;
84            bestStr = et.s.substr(end - bestLen + 1, bestLen);
85        }
86    }
87    et.propagate_counts();
88
89    long long totalOcc = 0;
90    for (int v = 2; v < (int)et.t.size(); ++v) totalOcc += et.t[v].occ;
91
92    cout << "Distinct palindromes = " << et.distinct() << "\n";
93    cout << "Total palindromic substrings (with multiplicity) = " << totalOcc << "\n";
94    cout << "Longest palindromic substring = " << bestStr << " (len=" << bestLen << ")\n";
95    return 0;
96}
97

This version uses fixed 26-letter transitions for lowercase input, giving O(1) worst-case transition time. It maintains the current longest palindrome as characters are added. After building, it aggregates occurrences and sums them to get the total number of palindromic substrings (counting multiplicity).

Time: O(n) time with O(1) transitions per step; propagation O(n).Space: O(n + 26·|V|) = O(n) for fixed alphabet.
Online prefix stats: distinct palindromes and LPS length after each character
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Eertree {
5    struct Node { unordered_map<char,int> next; int link,len; Node():link(0),len(0){} };
6    vector<Node> t; string s; int last;
7    Eertree(){ init(); }
8    void init(){ t.clear(); s.clear(); t.resize(2); t[0].len=-1; t[0].link=0; t[1].len=0; t[1].link=0; last=1; }
9    int get_suff_link(int v,int pos,char c){ while(true){ int L=t[v].len; if(pos-1-L>=0 && s[pos-1-L]==c) return v; v=t[v].link; } }
10    int add_char(char c){ int pos=s.size(); s.push_back(c); int cur=get_suff_link(last,pos,c); if(t[cur].next.count(c)){ last=t[cur].next[c]; return last; } t.push_back(Node()); int id=t.size()-1; t[id].len=t[cur].len+2; t[cur].next[c]=id; if(t[id].len==1){ t[id].link=1; last=id; return last;} int linkCand=get_suff_link(t[cur].link,pos,c); t[id].link=t[linkCand].next[c]; last=id; return last; }
11};
12
13int main(){
14    ios::sync_with_stdio(false); cin.tie(nullptr);
15    string S; cin >> S; Eertree et; int best=0; vector<int> prefDistinct, prefLPS;
16    for(char c: S){ int v=et.add_char(c); best=max(best, et.t[v].len); prefDistinct.push_back((int)et.t.size()-2); prefLPS.push_back(best); }
17    for(size_t i=0;i<S.size();++i){ cout << "i=" << i << ": distinct=" << prefDistinct[i] << ", LPS_len=" << prefLPS[i] << "\n"; }
18    return 0;
19}
20

This demonstrates the Eertree’s online nature. After each insertion, we immediately report the number of distinct palindromes in the current prefix and the longest palindromic substring length so far. This is useful for streaming or prefix-query problems.

Time: Expected O(n) overall; each step amortized O(1).Space: O(n).
Advanced: Minimum palindromic partition in O(n) using series links
1#include <bits/stdc++.h>
2using namespace std;
3
4// Eertree with series links for O(n) palindromic partition DP.
5// Assumes lowercase letters 'a'..'z' for simplicity.
6struct Eertree {
7    struct Node {
8        int next[26];
9        int link, len;
10        int seriesLink; // series link
11        int diff;       // len[v] - len[link[v]]
12        Node(){ fill(begin(next), end(next), -1); link=0; len=0; seriesLink=0; diff=0; }
13    };
14    vector<Node> t; string s; int last;
15
16    Eertree(){ init(); }
17    void init(){ t.clear(); s.clear(); t.resize(2); t[0].len=-1; t[0].link=0; t[0].seriesLink=0; t[0].diff=0; t[1].len=0; t[1].link=0; t[1].seriesLink=0; t[1].diff=0; last=1; }
18
19    int get_suff_link(int v, int pos, char c){
20        while(true){ int L=t[v].len; if(pos-1-L>=0 && s[pos-1-L]==c) return v; v=t[v].link; }
21    }
22
23    int add_char(char c){
24        int pos = (int)s.size(); s.push_back(c);
25        int x = c - 'a';
26        int cur = get_suff_link(last, pos, c);
27        if(t[cur].next[x] != -1){ last = t[cur].next[x]; return last; }
28        t.push_back(Node()); int id = (int)t.size()-1;
29        t[id].len = t[cur].len + 2;
30        t[cur].next[x] = id;
31        if(t[id].len == 1){ t[id].link = 1; t[id].diff = 1; t[id].seriesLink = 1; last=id; return last; }
32        int linkCand = get_suff_link(t[cur].link, pos, c);
33        t[id].link = t[linkCand].next[x];
34        t[id].diff = t[id].len - t[t[id].link].len;
35        if(t[id].diff == t[t[id].link].diff) t[id].seriesLink = t[t[id].link].seriesLink; else t[id].seriesLink = t[id].link;
36        last = id; return last;
37    }
38};
39
40int main(){
41    ios::sync_with_stdio(false); cin.tie(nullptr);
42    string S; cin >> S; int n = (int)S.size();
43    Eertree et; vector<int> dp(n+1, (int)1e9); vector<int> best; best.assign(2, (int)1e9); // best[v] will be resized lazily
44    dp[0]=0;
45
46    auto ensure_best_size = [&](int sz){ if((int)best.size() < sz) best.resize(sz, (int)1e9); };
47
48    for(int i=1;i<=n;i++){
49        int v = et.add_char(S[i-1]);
50        ensure_best_size((int)et.t.size());
51        dp[i] = (int)1e9;
52        // Iterate over series links from the current last
53        for(int u = et.last; et.t[u].len > 0; u = et.t[u].seriesLink){
54            int sl = et.t[u].seriesLink;
55            int candIndex = i - (et.t[sl].len + et.t[u].diff);
56            // dp index candIndex is >= 0
57            best[u] = dp[candIndex];
58            if(et.t[u].diff == et.t[et.t[u].link].diff){
59                best[u] = min(best[u], best[et.t[u].link]);
60            }
61            dp[i] = min(dp[i], 1 + best[u]);
62        }
63    }
64
65    cout << dp[n] << "\n"; // minimum number of palindromic substrings covering S
66    return 0;
67}
68

This program computes the minimum number of palindromic substrings needed to partition the input string using an Eertree with series links and the classic O(n) DP optimization. For each position i, it follows the series links from the current last node and updates dp[i] using a constant number of candidates per group. The arrays diff and seriesLink compress DP transitions so the overall time is linear.

Time: O(n) time due to series-link grouping and O(1) amortized updates per position.Space: O(n) for the Eertree plus O(n) for dp and auxiliary arrays.