1. Tight Bound for the Number of Distinct Palindromes in a Tree
- Author
-
Gawrychowski, Paweł, Kociumaka, Tomasz, Rytter, Wojciech, and Waleń, Tomasz
- Subjects
FOS: Computer and information sciences ,TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES ,Computational Theory and Mathematics ,Computer Science::Discrete Mathematics ,Applied Mathematics ,Computer Science - Data Structures and Algorithms ,Discrete Mathematics and Combinatorics ,Data Structures and Algorithms (cs.DS) ,Geometry and Topology ,F.2.2 ,MathematicsofComputing_DISCRETEMATHEMATICS ,Theoretical Computer Science - Abstract
For an undirected tree with edges labeled by single letters, we consider its substrings, which are labels of the simple paths between two nodes. A palindrome is a word $w$ equal to its reverse $w^R$. We prove that the maximum number of distinct palindromic substrings in a tree of $n$ edges satisfies $\text{pal}(n)=O(n^{1.5})$. This solves an open problem of Brlek, Lafrenière, and Provençal (DLT 2015), who showed that $\text{pal}(n)=\Omega(n^{1.5})$. Hence, we settle the tight bound of $\Theta(n^{1.5})$ for the maximum palindromic complexity of trees. For standard strings, i.e., for trees that are simple paths, the maximum palindromic complexity is exactly $n+1$. We also propose an $O(n^{1.5} \log^{0.5}{n})$-time algorithm reporting all distinct palindromes and an $O(n \log^2 n)$-time algorithm finding the longest palindrome in a tree.
- Published
- 2023