Tight Bound for the Number of Distinct Palindromes in a Tree

Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1

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 $…