Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00742047
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 10:24:42 AM
Last modification on : Monday, June 8, 2020 - 10:54:02 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:18 AM

File

Extracting_Powers_and_Periods_...
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, et al.. Extracting powers and periods in a string from its runs structure. SPIRE, 2010, Los Cabos, Mexico. pp.258-269, ⟨10.1007/978-3-642-16321-0_27⟩. ⟨hal-00742047⟩

Share

Metrics

Record views

429

Files downloads

365