Optimal bounds for computing α-gapped repeats

Following (Kolpakov et al. , 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors of the form uvu with | u v | = | u | + | v | ≤ α | 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.

Authors

• Maxime Crochemore
• Roman Kolpakov
• Gregory Kucherov

Keywords

• Combinatorics on words
• Algorithms on strings
• Combinatorial algorithms
• Time complexity
• Repeats
• Gapped repeats
• Subrepetitions