Efficiently computing runs on a trie
Efficiently computing runs on a trie
复制标题
高效计算在 trie 上运行
DOI：
10.1016/j.tcs.2021.07.011
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Ryo Sugahara;Yuto Nakashima;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
一个最大的重复，或运行，在一个字符串中，是一个最大的周期子串，其最小的周期是最多一半的长度。在本文中，我们考虑运行对应于一个trie上的路径，或者换句话说，在一个有根的边标记的树，每个边标记有一个单一的符号，路径的端点必须是一个后代/祖先的其他。对于一个有n条边的trie，我们证明了运行次数小于n。我们还证明了trie中最大游程密度的一个渐近下界：lim n→∞ <$ρ T（n）/n> 0.9932348其中ρ T（n）是n边trie中最大游程数.此外，我们还展示了一个O（n log log n）时间和O（n）空间的算法来寻找所有运行。
A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where each edge is labeled with a single symbol, and the endpoints of the path must be a descendant/ancestor of the other. For a trie with n edges, we show that the number of runs is less than n. We also show an asymptotic lower bound on the maximum density of runs in tries: lim n→∞ ρ T (n)/n> 0.9932348 where ρ T (n) is the maximum number of runs in a trie with n edges. Furthermore, we also show an O (n log log n) time and O (n) space algorithm for finding all runs.