How to Learn Eertrees (Palindromic Trees): Distinct Palindromes, Suffix Links, Online Updates and Factorization

Wait, What? A string can have O(N²) palindromic occurrences, yet all of its distinct palindromic substrings can be represented in only O(N) nodes.

An eertree, also called a palindromic tree, is an online data structure whose nodes represent distinct palindromic substrings. It combines ideas reminiscent of tries and suffix-link structures, but its invariant is specialized to palindrome growth. It is especially useful when you need more than the longest palindrome: distinct palindrome identities, suffix relationships, occurrence counts, online updates or palindrome factorization.

Quick Read

One-sentence answer: an eertree creates one node per distinct palindrome and uses suffix links to find the longest palindromic suffix that can be extended when each new character arrives.

Beginner: understand palindromic suffixes and why distinct palindromes are fewer than occurrences.
Intermediate: learn the two roots, suffix links, transitions and online insertion.
Advanced: count occurrences, derive factorization methods and compare with Manacher and suffix structures.
Professional: reason about alphabet representation, linear-size guarantees, dynamic extensions, test invariants and choose the correct palindrome tool for the workload.

1. Distinct Palindromes Are the Right Objects

In a string such as aaaaa, many palindromic occurrences overlap. The palindrome a appears five times, aa four times, and so on. An eertree does not create one node for every occurrence. It creates one node for each distinct palindromic string: a, aa, aaa, aaaa, aaaaa.

A fundamental fact is that a string of length N has at most N distinct nonempty palindromic substrings. This makes a linear-size node representation possible.

2. Why Manacher’s Algorithm Is Not the Same Job

The existing Manacher article teaches how to compute palindrome radii around every centre in linear time. That is excellent for longest-palindrome queries, palindrome tests derived from radii and occurrence geometry. An eertree answers a different question: “What are the distinct palindromes, how are their palindromic suffixes connected, and how does this set evolve online?”

Use Manacher when centre/radius information is the natural output. Use an eertree when palindrome identity and relationships are the natural output.

3. The Two Special Roots

Most eertree implementations begin with two imaginary root nodes:

a node of length -1;
a node of length 0.

The length-0 root represents the empty palindrome. The length–1 root is a sentinel that makes odd-length extension logic work uniformly at string boundaries. These two roots remove many special cases that would otherwise appear when inserting the first character or constructing length-1 palindromes.

4. What One Ordinary Node Stores

len: length of the palindrome represented by this node;
link: suffix link to the longest proper palindromic suffix;
next[c]: transition to the palindrome formed by extending with character c;
occurrence data: optional counters or metadata for applications.

If node P represents a palindrome p, a transition by character c conceptually represents c + p + c when that palindrome occurs in the processed prefix.

5. The Key Online Question

Suppose a new character s[i] arrives. Which palindrome can it extend?

Start from the node representing the longest palindromic suffix of the previous prefix. For a candidate palindrome of length L, check whether the character immediately before that palindrome equals the new character:

s[i - L - 1] == s[i].

If not, follow the candidate’s suffix link to the next shorter palindromic suffix and try again. Eventually the length–1 root guarantees that the test succeeds.

6. Why Suffix Links Make This Fast

Suffix links skip directly between palindromic suffix candidates. If the current longest suffix palindrome cannot be wrapped by the new character, there is no need to test every shorter length. Follow the link to the longest smaller palindrome that is itself a suffix.

This is structurally similar to failure links in string-matching automata: the link says where to continue after the strongest current candidate fails. But the objects and extension rule are specifically palindromic.

7. Existing Transition or New Palindrome?

Once a suffix node v can be extended by the new character c, look for next[v][c].

If the transition exists, that distinct palindrome has appeared before. Make it the new longest suffix palindrome.
If it does not exist, create exactly one new node with length len[v] + 2.

This “at most one new palindrome per appended character” property is another way to see the linear-size bound.

8. Setting the New Node’s Suffix Link

For a new length-1 palindrome, the suffix link points to the length-0 root. For a longer new palindrome, begin from the suffix link of v, follow suffix links until another palindrome can be extended by c, then set the new node’s suffix link to that transition.

Conceptually: “After removing the outermost matching characters from the new palindrome, what is its longest proper palindromic suffix?” The suffix-link search answers that question incrementally without scanning the whole string.

9. Online Insertion Skeleton

append(c):
    s.push(c)
    v = longest_suffix

    while s[i - len[v] - 1] != c:
        v = link[v]

    if next[v][c] exists:
        longest_suffix = next[v][c]
        count[longest_suffix] += 1
        return

    u = new_node(len[v] + 2)
    next[v][c] = u

    if len[u] == 1:
        link[u] = root_len_0
    else:
        w = link[v]
        while s[i - len[w] - 1] != c:
            w = link[w]
        link[u] = next[w][c]

    longest_suffix = u
    count[u] += 1

The exact boundary technique varies. Many implementations prepend a sentinel character so the index test is always valid. Whatever convention you use, make it explicit and test it before optimizing.

10. A Small Trace: “ababa”

As characters arrive, new distinct palindromes appear:

a creates node “a”;
b creates node “b”;
the next a creates “aba”;
the next b creates “bab”;
the final a creates “ababa”.

Shorter palindromes such as “a” occur again but do not require new nodes. The eertree records identity once and occurrence information separately.

11. Counting Total Occurrences

During online construction, increment a node when it becomes the longest palindromic suffix of a processed prefix. Those direct counts do not yet equal total substring occurrences, because every occurrence of a longer palindrome also contributes an occurrence to its palindromic suffixes.

After construction, process nodes in decreasing length and add each node’s count to its suffix-link parent. The propagated counts then give the total number of occurrences of every distinct palindrome.

12. Distinct Count and Longest Palindrome Become Easy

The number of ordinary nodes is the number of distinct nonempty palindromes. The maximum node length is the longest palindrome. These outputs require no separate centre scan once the eertree has been built.

That does not make eertree “better than Manacher.” It means the representation stores a different set of useful facts.

13. Time and Space Complexity

The eertree uses O(N) nodes and O(N) structural space, excluding the representation chosen for outgoing transitions. The original Rubinchik–Shur work gives online construction with linear-size storage and efficient processing; with map-based transitions over a general alphabet, a common bound is O(N log σ), where σ is the number of distinct alphabet symbols relevant to transition lookup. With a fixed small alphabet and array transitions, lookup can be O(1), giving linear-time construction in the standard implementation model.

Always include transition representation in your complexity claim. A node with a full array of 256 or 65,536 entries has very different memory behaviour from a node with a compact map.

14. Alphabet Engineering

Lowercase a–z: fixed arrays are simple and fast.
Moderate known alphabet: arrays or small vectors may still be appropriate.
Unicode or large sparse symbol set: maps, hash maps or compressed symbol IDs avoid huge per-node tables.

Professional implementations separate the abstract transition interface from the alphabet storage choice.

15. Palindromic Factorization

Once palindromic suffixes are linked explicitly, dynamic programming over palindrome partitions becomes much more structured. The original eertree work develops algorithms for palindromic length and k-factorization, and later work improves several factorization problems further.

The beginner should not start with these optimizations. First be able to enumerate palindromic suffix nodes for each prefix. Then a recurrence such as “minimum pieces ending here” becomes easier to see: each suffix palindrome defines one valid final factor.

16. Series Links and Advanced Acceleration

Advanced eertree techniques group suffix-link chains by regular differences in palindrome lengths. Series links can accelerate partition and factorization dynamic programs by skipping repetitive suffix patterns. Learn ordinary suffix links first; series-link code is almost impossible to reason about if the base tree invariant is not automatic.

17. Sliding Windows and Double-Ended Extensions

Research after the original eertree introduced structures for sliding windows and for updates at both ends of the stored string. Mieno and collaborators studied palindromic trees over a moving window, while later double-ended eertree work supports deque-like changes and range-query applications.

These results show the idea is not confined to contest tricks. The original online representation became a foundation for a broader family of palindrome data structures.

18. Eertree Versus Other String Structures

Manacher: palindrome radius at every centre; ideal for longest-palindrome geometry.
Suffix array/LCP: lexicographic suffix ordering and repeated-substring structure.
Suffix automaton: compact state machine for all substrings and end-position equivalence.
Aho–Corasick: many-pattern matching through trie transitions and failure links.
Eertree: distinct palindromes, palindromic suffix links and online palindrome growth.

Choose by the object your later algorithm needs. “String problem” is not enough information to select a data structure.

19. Correctness Proof Structure

Node invariant: every ordinary node represents one distinct palindrome that occurs in the processed prefix.
Transition invariant: next[v][c] represents the palindrome formed by wrapping v’s palindrome with c.
Suffix-link invariant: link[v] is the longest proper palindromic suffix of v.
Online invariant: longest_suffix is the longest palindromic suffix of the entire processed prefix.

When appending one character, any newly created palindrome must be a suffix of the new prefix. Following suffix links finds the longest extendable old suffix; adding the new character around it creates the only possible new distinct palindrome. This preserves the invariants inductively.

20. Common Failure States

Forgetting the length–1 root and accumulating boundary special cases.
Setting a new node’s suffix link to v instead of searching from link[v].
Counting only times a node is the longest suffix and calling that total occurrences.
Confusing transition edges with suffix links.
Using a fixed transition array whose alphabet cost dominates O(N) node storage.
Assuming every palindrome occurrence creates a node.
Choosing an eertree for a task Manacher solves more simply.
Copying series-link optimizations before the base suffix-link construction is verified.

21. Testing Strategy

For short random strings, enumerate every substring by brute force, keep those equal to their reversals, and compare the resulting set with the eertree nodes. For each node, independently compute its longest proper palindromic suffix and compare it with the stored suffix link. Then compare propagated occurrence counts with brute-force substring counts.

Use adversarial families: all one character, all distinct characters, alternating strings such as abababab, even palindromes, odd palindromes and strings where the longest suffix changes sharply after each append.

22. Practice Ladder: Beginner to Professional

Level 1: list all distinct palindromes of a five-character string.
Level 2: for every prefix, mark its longest palindromic suffix.
Level 3: draw the two roots, nodes and suffix links for “ababa”.
Level 4: implement online insertion with fixed-alphabet transitions.
Level 5: propagate occurrence counts through suffix links.
Level 6: compare eertree output with Manacher on the same strings and explain which information each representation makes easy.
Level 7: solve a palindrome-partition dynamic program by iterating palindromic suffixes.
Level 8: study series links, sliding-window or double-ended eertree extensions and justify their extra machinery.

23. How to Learn This Efficiently

Start with a completed tree for one short string and predict what changes when one character is appended. Then run the insertion and inspect only three subgoals: “find extendable suffix,” “reuse or create node,” and “set suffix link.” Next modify the alphabet or add occurrence counting. Only after several traces should you write the structure from a blank editor.

This staged approach matches useful programming-education evidence. PRIMM emphasizes prediction, code reading and modification before full creation; subgoal-labelled worked examples help novices see the purpose of each code region; Parsons-style tasks can isolate the order of suffix-link steps without making syntax the main difficulty.

24. Learning Hall Boundary

This article owns the public educational job of eertrees/palindromic trees and their distinct-palindrome representation. It complements the existing Manacher, suffix-array, suffix-automaton and multi-pattern-string articles rather than duplicating them. It does not redefine MindOS, Bolt or Student/Studying Interface jobs and does not expose private eduKateAI architecture, prompts, routing, benchmarks, scoring or implementation details.

Sources and Further Reading

Mikhail Rubinchik and Arseny M. Shur, EERTREE: An Efficient Data Structure for Processing Palindromes in Strings, European Journal of Combinatorics 68, 249–265, 2018, DOI 10.1016/j.ejc.2017.07.021.
Takuya Mieno and collaborators, Palindromic Trees for a Sliding Window and Its Applications, 2020.
Qisheng Wang, Ming Yang and Xinrui Zhu, work on double-ended palindromic trees and range applications, 2022.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming-education research, 2019; code reading, prediction and structured modification.
Lauren E. Margulieux, Briana B. Morrison and Adrienne Decker, research on subgoal-labelled worked examples, 2020.

Professional rule: use an eertree when distinct palindrome identity, suffix relationships or online palindrome structure are first-class requirements. If the job is only longest-palindrome radii, keep the simpler Manacher representation.