Skip to content
Tutorials Center
My learning

Topics

Lesson 211 of 225 ยท Advanced Topics

Palindromic Tree (Eertree)

Build an eertree in Python: add characters one at a time, follow suffix links, and count every distinct palindromic substring of a string in linear time.

Manacher's algorithm finds the palindrome around every center. Sometimes you need a different view: the set of all distinct palindromic substrings of a string, how often each one occurs, and those answers after every new character is appended. The structure made for this is the palindromic tree, also called the eertree (published in 2014).

The key fact behind it is short and surprising: a string of length n contains at most n distinct non-empty palindromic substrings. Each new character adds at most one new palindrome. So a tree with one node per distinct palindrome has only n + 2 nodes, and it can be built in O(n) time for a small alphabet.

Why at most one new palindrome per character

Suppose you append a character c to a string. Any palindrome that is new must end at the new position, so it is a suffix of the new string. Look at the longest palindromic suffix. Every shorter palindromic suffix is also a prefix of that longest one (a palindrome reads the same backwards), so it already occurred earlier in the string. Hence only the longest palindromic suffix can possibly be new, and at most one palindrome appears per step.

The structure

Each node stands for one distinct palindrome and stores:

  • length: the length of the palindrome.
  • edges: a map from a character c to the node for c + P + c, where P is this node's palindrome. An edge wraps the palindrome with the same letter on both sides.
  • link: the suffix link, the node of the longest proper palindromic suffix of this palindrome.

There are two special roots. The imaginary node has length -1: wrapping it with c produces the single letter c. The empty node has length 0: wrapping it produces cc. The empty root links to the imaginary one, and the imaginary root links to itself.

For the string eye, the palindromes are e, y and eye:

graph LR
    I["imaginary (-1)"] -->|e| E["e (1)"]
    I -->|y| Y["y (1)"]
    Z["empty (0)"]
    Y -->|e| EYE["eye (3)"]
    EYE -.suffix link.-> E
    E -.suffix link.-> Z
    Y -.suffix link.-> Z
    Z -.suffix link.-> I

Solid edges wrap a palindrome: from y, the edge labeled e leads to e + y + e. Dashed arrows are suffix links.

Adding a character

Keep last, the node of the longest palindromic suffix of the string so far. To add the character at position i:

  1. Starting at last, follow suffix links until you reach a node whose palindrome can be wrapped by s[i]: the character just before it, s[i - length - 1], must equal s[i]. The imaginary root always works, since its length -1 makes that check look at s[i] itself.
  2. If that node already has an edge labeled s[i], the palindrome exists. Set last to its child.
  3. Otherwise create a node of length length + 2. To get its suffix link, follow suffix links from the link of the node you stopped at with the same test and take the edge labeled s[i] (a new single letter simply links to the empty node). Add the edge and set last to the new node.

Every suffix-link jump makes the candidate palindrome shorter, and the total number of jumps over the whole build is amortized O(n), much like the failure function in pattern matching.

Python Build an eertree and list its palindromes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The string abacaba has length 7 and exactly 7 distinct palindromes (a, b, c, aba, aca, bacab, abacaba), and the first step adds a, the second b, and so on; steps that find an existing palindrome add nothing.

Checking against brute force

Whenever you implement a clever structure, test it against a slow, obviously correct version on random inputs.

Python Eertree versus brute force on random strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting occurrences

Often you want not only the distinct palindromes but how many times each occurs. When you add a character, the node last is the longest palindromic suffix ending there. That gives one occurrence to it, and by the suffix-link structure it is also an occurrence of every palindrome on its suffix-link chain. So:

  1. While building, add 1 to count[last] after each character.
  2. At the end, go through the nodes from newest to oldest and add each node's count to the count of its suffix link. A node's link is always an older node, so this order is safe.

The total number of palindromic substrings counting repeats is the sum of all counts. The longest palindromic substring is simply the node with the greatest length.

Python Occurrences of every palindrome

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Eertree or Manacher?

Manacher Eertree
Longest palindromic substring Yes, O(n) Yes
Count palindromic substrings (with repeats) Yes, via radii Yes, via counts
Distinct palindromes No Yes, directly
Works online (append one character at a time) Awkward Yes, natural
Memory O(n) integers O(n) nodes with maps

Pick Manacher for a one-shot "longest palindrome" question, and the eertree when you need distinct counts, per-palindrome occurrence data, or palindromic structure after every prefix. It also underlies problems on palindromic factorizations, such as the fewest pieces to cut a string into palindromes, solved with a dynamic program over the series links.

Common mistakes

  • Forgetting the two roots, or giving the imaginary root a suffix link to anything but itself.
  • Computing the new node's suffix link from cur instead of from link[cur]; starting at cur finds the node itself.
  • Adding the edge from cur to the new node before looking up the suffix link. The lookup could then find the new node itself and link it to itself. Compute the link first.
  • Propagating counts in creation order instead of newest first.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the maximum number of distinct non-empty palindromic substrings in a string of length n?

    Appending one character creates at most one new palindrome, the longest palindromic suffix, because every shorter one already appeared earlier as a prefix of it.
  2. 2. In an eertree, what does an edge labeled c from node P lead to?

    Edges wrap a palindrome with the same character on both sides, which is why the two root nodes of length -1 and 0 are needed to create odd and even palindromes.
  3. 3. What is stored in the suffix link of a node?

    The link points to the node of the longest palindrome that is a proper suffix of this one. Following links from last visits all palindromic suffixes of the current string, from longest to shortest.
  4. 4. How do you turn per-step counts into total occurrences of each palindrome?

    A palindrome that ends at a position also gives an occurrence of every palindrome on its suffix-link chain. Processing newest to oldest makes sure counts have been fully collected before they are passed down.

Summary

  • A string of length n has at most n distinct palindromic substrings, because each appended character creates at most one new one.
  • The eertree has one node per distinct palindrome, plus two roots of length -1 and 0.
  • Edges wrap a palindrome with a letter; suffix links point to the longest proper palindromic suffix.
  • Adding a character follows suffix links from last to find where the new letter can wrap a palindrome, then creates at most one node.
  • Construction is amortized O(n) for a small alphabet; counts propagated along suffix links give all occurrences.
  • Use it for distinct counts, online updates and palindromic factorizations; use Manacher for a quick longest palindrome.

Next: Suffix Arrays and Suffix Trees