Name
Abstract | ||
|---|---|---|
A maximal repetition, or run, in a string, is a periodically maximal 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 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 $O(nsqrt{log n}log log n)$ time and $O(n)$ space algorithm for counting and finding the shallower endpoint of all runs. We further show an $O(nsqrt{log n}log^2log n)$ time and $O(n)$ space algorithm for finding both endpoints of all runs. |
Year | Venue | Field |
|---|---|---|
2019 | Combinatorial Pattern Matching | Binary logarithm,Discrete mathematics,Combinatorics,Substring,Trie,Mathematics |
DocType | Volume | Citations |
Journal | abs/1901.10633 | 0 |
PageRank | References | Authors |
0.34 | 7 | 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 |