 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
Extracting powers and periods in a string from its runs structure
Abstract : A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a string 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 a few classical string problems: computing all distinct kth string powers for a given k, in particular squares for k = 2, and finding all local periods in a given string of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a string and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov & Kucherov, 1999). 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.
Cited literature [15 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00742047
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 10:24:42 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:18 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:18 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 10:24:42 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:18 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:18 AM
File
Extracting_Powers_and_Periods_...
Files produced by the author(s)