Optimal bounds for computing α-gapped repeats

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Citations (Scopus)

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(α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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings
EditorsBianca Truthe, Jan Janoušek, Adrian-Horia Dediu, Carlos Martín-Vide
PublisherSpringer Verlag
Pages245-255
Number of pages11
ISBN (Print)9783319299990
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event10th International Conference on Language and Automata Theory and Applications, LATA 2016 - Prague, Czech Republic
Duration: 14 Mar 201618 Mar 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9618
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Language and Automata Theory and Applications, LATA 2016
Country/TerritoryCzech Republic
CityPrague
Period14/03/1618/03/16

Fingerprint

Dive into the research topics of 'Optimal bounds for computing α-gapped repeats'. Together they form a unique fingerprint.

Cite this