Eertree Palindromic Suffix Links
Build one node per distinct palindrome and follow the suffix links that make online updates possible.
By Riano · Published · Updated · Report a correction
Eertree Palindromic Suffix Links
An eertree, or palindromic tree, is a specialized data structure used to efficiently process and count distinct palindromes within a string. By representing palindromes and their relationships directly, it makes online updates possible in optimal time.
Worked Example: "abacaba"
Let's trace the construction of the eertree for the word abacaba with a prefix length of 7. The tree initially has two roots: one of length -1 for odd-length palindromes, and one of length 0 for even-length palindromes.
Word: "abacaba"
1. a -> Palindrome "a" (len 1, suffix link root(0))
2. b -> Palindrome "b" (len 1, suffix link root(0))
3. a -> Palindrome "aba" (len 3, suffix link "a")
4. c -> Palindrome "c" (len 1, suffix link root(0))
5. a -> Palindrome "aca" (len 3, suffix link "a")
6. b -> Palindrome "bacab" (len 5, suffix link "b")
7. a -> Palindrome "abacaba" (len 7, suffix link "aba")
Total distinct palindromes: 7 ("a", "b", "aba", "c", "aca", "bacab", "abacaba")
Longest suffix length: 7 ("abacaba")
Suffix link of longest suffix points to: "aba" (length 3)Experiment with the Module
Follow these steps to observe the eertree's state changes in real time:
- Open the Eertree Palindromic Suffix Links module.
- Select the Word "Nested" and Prefix length 7 to see the diagram form the tree structure exactly as described above.
- Change the Word to "Alternating" (abababababab) and Prefix length 12. Observe how the number of distinct palindromes scales linearly and the suffix links point sequentially to smaller prefixes.
- Change the Prefix length to 0. Notice the tree initializes with only the two roots and returns 0 distinct palindromes.
Limitations and Boundaries
The eertree structure efficiently handles operations across distinct palindromes by storing paths and suffix links dynamically. However, its memory requirements depend strictly on the alphabet size since each node requires space for character extension edges. In addition, providing a prefix length larger than the word length is an invalid boundary case explicitly handled to return unavailable states, as characters outside the string domain cannot be processed.
References
Mikhail Rubinchik, Arseny M. Shur. Eertree: An Efficient Data Structure for Processing Palindromes in Strings (2015). https://arxiv.org/abs/1506.04862
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Eertree Palindromic Suffix Links module.
Try Eertree Palindromic Suffix Links on Riano →