Extracting powers and periods in a string from its runs structure

Maxime Crochemore (1, 2) , Costas S. Iliopoulos (1) , Marcin Kubica (3) , Jakub Radoszewski (3) , Wojciech Rytter (3) , Tomasz Walen (3)

1 Informatics
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 Institute of Informatics [Warsaw]

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.

Domaines: Algorithme et structure de données [cs.DS]

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⟩