Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Extracting Powers and Periods in a String from Its Runs Structure
verfasst von : Maxime Crochemore, Costas Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
k
th 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.