TY - GEN

T1 - Optimal bounds for computing α-gapped repeats

AU - Crochemore, Maxime

AU - Kolpakov, Roman

AU - Kucherov, Gregory

PY - 2016

Y1 - 2016

N2 - Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α2n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

AB - Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α2n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn+S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

UR - http://www.scopus.com/inward/record.url?scp=84960422686&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-30000-9_19

DO - 10.1007/978-3-319-30000-9_19

M3 - Conference contribution

AN - SCOPUS:84960422686

SN - 9783319299990

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 245

EP - 255

BT - Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings

A2 - Truthe, Bianca

A2 - Janoušek, Jan

A2 - Dediu, Adrian-Horia

A2 - Martín-Vide, Carlos

PB - Springer Verlag

T2 - 10th International Conference on Language and Automata Theory and Applications, LATA 2016

Y2 - 14 March 2016 through 18 March 2016

ER -