Structure
Node per distinct palindrome. Suffix link to longest proper palindromic suffix. Transitions extend by 1 char on each side.
Advertisement
Number of palindromes
String of length N has ≤ N+1 distinct palindromes. Eertree has one node per + two roots.
Advertisement
Online construction
Amortized O(σ) per character. Total O(N) build.
Applications
Count distinct palindromes. Longest palindromic subsequence variants. Palindromic factorization.