Name
Abstract | ||
|---|---|---|
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 ->infinity), rho(T)(n)/n> 0.9932348 where rho(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. (C) 2021 The Authors. Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.07.011 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Maximal repetitions, Lyndon words, Trie | Journal | 887 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryo Sugahara | 1 | 0 | 0.68 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 9 | 13.78 |