Name
Abstract | ||
|---|---|---|
A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is O(n) and that they can all be computed in O(n) time. We study some applications of this result. New simpler O(n) time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for k=2, and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25,26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2013.11.018 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Lyndon structure,runs structure,distinct k-th word power,Lyndon word,computing power,length n,Manhattan skyline problem,time algorithm,Extracting power,new simpler O,classical textual problem,efficient algorithm | Journal | 521, |
ISSN | Citations | PageRank |
0304-3975 | 16 | 0.67 |
References | Authors | |
25 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| maxime crochemore | 1 | 73 | 6.84 |
| C. S. Iliopoulos | 2 | 52 | 6.67 |
| M. Kubica | 3 | 30 | 2.52 |
| jakub radoszewski | 4 | 32 | 2.90 |
| wojciech rytter | 5 | 130 | 17.13 |
| Tomasz Waleń | 6 | 706 | 39.62 |