Optimal Bounds for Computing α-gapped Repeats

Abstract : 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(α 2 n) 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.
Type de document :
Communication dans un congrès
10th International Conference on Language and Automata Theory and Applications (LATA), , Mar 2016, Prague, Czech Republic. Springer, Lecture Notes in Computer Science 9618, pp.245 - 255, 2016, Language and Automata Theory and Applications. 〈10.1007/978-3-319-30000-9_19〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-auf.archives-ouvertes.fr/hal-01577120
Contributeur : Gregory Kucherov <>
Soumis le : jeudi 24 août 2017 - 22:13:37
Dernière modification le : jeudi 26 octobre 2017 - 11:28:01

Fichier

main-lncs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov. Optimal Bounds for Computing α-gapped Repeats. 10th International Conference on Language and Automata Theory and Applications (LATA), , Mar 2016, Prague, Czech Republic. Springer, Lecture Notes in Computer Science 9618, pp.245 - 255, 2016, Language and Automata Theory and Applications. 〈10.1007/978-3-319-30000-9_19〉. 〈hal-01577120〉

Partager

Métriques

Consultations de la notice

97

Téléchargements de fichiers

34