Eertree Palindromic Suffix Links
Build one node per distinct palindrome and follow the suffix links that make online updates possible.
Free theory articleBuild one node per distinct palindrome and follow the suffix links that make online updates possible.
Concept & interpretation
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.
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.