Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings.

For δ  ∈  ℝ + , maximal δ -repetitions (δ -subrepetitions) are fractional powers in strings with exponent of at least 2 + δ (and 1 + δ , respectively) which are non-extendable with respect to their minimum period. In this paper, we show that in a string S with string attractor Γ there are at most (| Γ | + 2) (⌊ 3 + 6 δ ⌋ ⋅ ⌊ log 1 + δ 4 (| S |) ⌋ + 2) distinct (unpositioned) extended maximal δ -repetitions. Also for any natural number q ≥ 2 the string contains at most (| Γ | + 2) (⌊ 3 + 4 δ ⌋ ⋅ ⌊ log 1 + δ 2 q (| S |) ⌋ + 2) distinct extended maximal δ -subrepetitions without q th powers. We further prove that for fixed δ and q ≥ ⌈ δ + 4 ⌉ , both upper bounds are tight up to a constant factor. [ABSTRACT FROM AUTHOR]