Tight Bound for the Number of Distinct Palindromes in a Tree

08/30/2020
by   Paweł Gawrychowski, et al.
0

For an undirected tree with n edges labelled by single letters, we consider its substrings, which are labels of the simple paths between pairs of nodes. We prove that there are O(n^1.5) different palindromic substrings. This solves an open problem of Brlek, Lafrenière, and Provençal (DLT 2015), who gave a matching lower-bound construction. Hence, we settle the tight bound of Θ(n^1.5) for the maximum palindromic complexity of trees. For standard strings, i.e., for paths, the palindromic complexity is n+1. We also propose O(n^1.5logn)-time algorithm for reporting all distinct palindromes in an undirected tree with n edges.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset