Computing palindromes and suffix trees of dynamic trees

Abstract We consider the problems of computing maximal palindromes and distinct palindromes in an edge-labeled rooted tree where each edge is labeled by a single character. Such a tree is a natural generalization of a string, which can be seen as a single-path tree. There is a linear time offline algorithm to compute maximal palindromes and distinct palindromes in a given (static) tree whose edge-labels are drawn from a linearly-sortable alphabet Mieno et al., ISAAC 2022. In this paper, we tackle problems of palindrome enumeration on dynamic trees which support leaf additions and leaf deletions. We propose the first sub-quadratic algorithms to enumerate palindromes in a dynamic tree whose edge-labels are drawn from a general ordered alphabet. Our algorithm computes all maximal palindromes in O(N log h) time and all distinct palindromes in O(N log h + N log s) time with O(N) working space, where N is the number of edges in the tree, h is the height of the tree, and s is the number of distinct characters appearing in the tree. Furthermore, as a by-product, we present an O(N log N)-time online algorithm to construct the suffix tree of the input tree, which is of independent interest.