Almost Optimal Searching of Maximal Subrepetitions in a Word

Abstract

For some fixed δ such that 0δ1, a δ-subrepetition in a word is a factor whose exponent is less than 2 but is not less than 1+δ (the exponent of the factor is the ratio of the factor length to its minimal period). The δ-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter while preserving its minimal period. In the paper, we propose an algorithm for searching all maximal δ-subrepetitions in a word of length n in O(nδlog1δ) time (the lower bound for this time is Ω(nδ)). It improves the previous known time complexity bounds for solving this problem.

Keywords

• combinatorics on words
• combinatorial algorithms
• time complexity
• repetitions