论文标题
紧密绑定了一棵树中不同的回文的数量
Tight Bound for the Number of Distinct Palindromes in a Tree
论文作者
论文摘要
对于一棵带有单个字母标记的$ n $边缘的无向树，我们考虑其子字母，它们是节点对之间简单路径的标签。我们证明有$ o（n^{1.5}）$不同的palindromic子字符串。这解决了Brlek，Lafrenière和Provençal（DLT 2015）的空旷问题，他们提供了相配的下限结构。因此，我们解决了$θ（n^{1.5}）$的紧密界限，以最大程度地对树木的综合性。对于标准字符串，即，对于路径，allindromic的复杂性为$ n+1 $。我们还建议$ o（n^{1.5} \ log {n}）$ - 时间算法，用于报告带有$ n $ edges的无向树中所有不同的palindromes。
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.5} \log{n})$-time algorithm for reporting all distinct palindromes in an undirected tree with $n$ edges.
