Eertree, in depth: the palindromic tree, two roots, suffix-link walks, linear-time construction and counting palindromes

At most n distinct palindromes

Everything rests on one fact: a string of length n has at most n distinct non-empty palindromic substrings. That is very few, compared with up to n(n+1)/2 substrings of all kinds.

The proof is short. Add characters one at a time. When you append a character c, any new palindrome must end at the new position. Let P be the longest palindromic suffix of the string so far. Any shorter palindromic suffix Q of P is also a prefix of P, because P reads the same backwards. So Q already occurred earlier, at the start of P. Only P itself can be new. Each character adds at most one new palindrome, so n characters add at most n.

This bound tells you three things about the eertree: it has at most n + 2 nodes (the 2 are the roots), each insertion creates at most one node, and the work per insertion is finding P. Most of the design is about finding P quickly.

Nodes, edges, roots and suffix links

Each node is one distinct palindrome. A node stores its length, its outgoing edges and a suffix link.

• Edges. An edge labelled c goes from the node for X to the node for cXc. Palindromes grow outwards from the centre, one character on each side, so every palindrome hangs below the one it was grown from.
• Two roots. Root 0 has length 0 and stands for the empty string, so its edge c leads to cc, the even palindromes. Root -1 is an imaginary palindrome of length -1. Adding c on both sides of it gives a string of length -1 + 2 = 1, the single letter c. This trick lets odd and even palindromes use the same insertion code.
• Suffix links. The suffix link of node X points to the longest proper suffix of X that is also a palindrome. Single letters link to root 0, root 0 links to root -1, and root -1 links to itself.
• Last. The structure also tracks the node of the longest palindromic suffix of the text so far, called last.

Inserting a character

To append character c at position i, start from last and follow suffix links until you find a palindrome X such that the character just before X equals c, that is, s[i - 1 - len(X)] == c. Then cXc is the longest palindromic suffix of the new string. Root -1 always succeeds, because i - 1 - (-1) = i, so it compares c with itself. That ends the walk.

If X already has an edge c, the palindrome cXc exists. Increase its occurrence counter and make it last. Otherwise create a node of length len(X) + 2. Its suffix link needs a second walk. Start from the suffix link of X and find the next palindrome Y that c can extend, then link the new node to the child of Y along c. If the new node has length 1, link it to root 0 directly.

class Eertree:
    def __init__(self):
        self.length = [-1, 0]     # node 0: root -1, node 1: root 0 (empty)
        self.link = [0, 0]        # root 0 links to root -1; root -1 to itself
        self.next = [{}, {}]
        self.occ = [0, 0]
        self.last = 1
        self.s = []

    def _extendable(self, v, i):
        while True:
            j = i - 1 - self.length[v]
            if j >= 0 and self.s[j] == self.s[i]:
                return v
            v = self.link[v]

    def add(self, ch):
        self.s.append(ch); i = len(self.s) - 1
        x = self._extendable(self.last, i)
        if ch in self.next[x]:                     # palindrome already known
            self.last = self.next[x][ch]
            self.occ[self.last] += 1
            return False
        w = len(self.length)
        self.length.append(self.length[x] + 2)
        self.next.append({}); self.occ.append(1)
        if self.length[w] == 1:
            self.link.append(1)                    # single letter -> empty root
        else:
            y = self._extendable(self.link[x], i)
            self.link.append(self.next[y][ch])     # always exists: shorter, seen before
        self.next[x][ch] = w                       # attach AFTER computing the link
        self.last = w
        return True

Two lines in this code are where implementations most often break. The j >= 0 check stops the walk from reading before the start of the string. Without it, Python silently reads s[-1]. The single-letter case must link to root 0 explicitly. Root -1 links to itself, so if a new letter went through the second walk, the walk would return root -1 and the new node would link to itself.

Worked example: building eertree

Build the tree for "eertree". Positions are 0 to 6. Here every character happens to create a new node, so the tree ends with exactly n = 7 palindromes, meeting the bound.

Check the last row. The new node eertree comes from X = ertre. For its suffix link, the second walk starts at the link of ertre, which is e. The character before that e suffix is at position 6 - 1 - 1 = 4, which is r, not e, so the walk moves on to root 0. There the character before is at position 5, which is e. It matches, so Y is root 0 and the link goes to its e child, ee. That is right: the longest proper palindromic suffix of eertree is ee.

A brute-force check that lists every substring and keeps the palindromes finds the same seven: e, ee, r, t, rtr, ertre and eertree. Always keep a brute-force oracle like this around while developing. On random strings over a two-letter alphabet, which are full of palindromes, it catches every off-by-one bug quickly.

Why construction is linear

Each insertion can follow many suffix links, so why is the total linear? Track the start position of last, the longest palindromic suffix. Each step of the first walk moves that start position strictly to the right. Appending a character can move it left by at most one, since the new palindrome cXc starts one position before X. The start position never exceeds n, so the total number of steps over the whole string is at most about 2n. A similar argument, using the start position of the suffix-link target, bounds the second walk.

With a hash map or a sorted list per node for edges, the total time is O(n log sigma) or O(n) expected, where sigma is the alphabet size. With a fixed array of sigma slots per node, edge lookups are O(1) and memory is O(n sigma). For lowercase text, 26 integers per node is fine. For bytes or Unicode it is not.

One warning. The bound is amortised over a run of appends. If you also delete characters, for example to undo during a backtracking search, an adversary can make you repeat a long walk again and again. Undo by restoring the saved last and node count, which is O(1). If you need guaranteed time per append under undo, use the "direct link" variants from the original paper, which store for each node and letter the target of the walk.

Answering queries

Once built, most palindrome questions become short loops over the nodes.

The occurrence count works because each time a palindrome occurs as the longest suffix, all its palindromic suffixes occur there too. The raw occ counts only the longest one. Pushing counts down the suffix links, longest first, fixes that. Nodes are created in order of increasing end position, and a suffix link always points to an older node, so reverse creation order processes children before their link targets. No sort is needed.

t = Eertree()
for ch in "eertree":
    t.add(ch)
for v in range(len(t.length) - 1, 1, -1):    # skip both roots
    t.occ[t.link[v]] += t.occ[v]
# t.occ now holds the true occurrence count of every palindrome node

For depth, store depth[w] = depth[link[w]] + 1 when you create a node, with both roots at depth 0. Then the number of palindromes ending at position i is depth[last], in O(1), while streaming.

How it compares

These tools work well together. Manacher's algorithm is the simpler choice if you only need maximal palindromes. Polynomial hashing answers palindrome tests for arbitrary ranges, which the eertree does not. The suffix automaton is the eertree's cousin for all substrings, and it uses the same ideas: suffix links and amortised walks.

For dynamic programming over palindromic factorisations, such as splitting a string into the fewest palindromes, the eertree is the base for a further structure called series links, which groups suffix-link chains into arithmetic progressions so the DP runs in O(n log n). Palindrome partitioning, min cuts develops that.

Engineering notes

• Store nodes as parallel arrays. Use length, link, occ and edges as arrays indexed by node ID, preallocated to n + 2. This is faster and smaller than node objects, and it makes undo a matter of resetting a counter.
• Pick the edge representation by alphabet. Use a fixed array for small alphabets. For large ones, use a single global hash map keyed by (node, char), not a map per node.
• Avoid recursion. Both walks are loops. Any traversal of the tree, such as listing palindromes, should use an explicit stack, because the tree can be n levels deep on a string like "aaaa...".
• Reconstruct strings lazily. Store for each node one end position. The palindrome is the substring of that length ending there, so you never store the strings themselves.
• Test with an oracle. Compare distinct sets and counts with brute force on thousands of random strings over alphabets of size 1, 2 and 3. Include the empty string and strings of one repeated letter.

What to do next

1. Type in the class above and build "eertree". Check the node table against the trace.
2. Add the brute-force oracle and run it on 10,000 random strings over the alphabet {a, b}.
3. Add depth and occurrence propagation. Confirm the total of 12 palindromic substrings for "eertree".
4. Solve a counting problem with it, such as the number of distinct palindromic substrings of a 100,000-character string, and time it against a hashing solution.
5. Add undo by saving last and the node count, and use it in a backtracking search.
6. Read the partitioning article to see series links built on top of this tree.