Our results improve those of [1]} (as well as those existing in the literature before [1]}), where the size of the set of maximal \(\alpha \) -gapped repeats with non-empty gap is shown to be \({\mathcal {O}}(\alpha ^2 n)\) , and can be computed in \({\mathcal {O}}(\alpha ^2 n)\)  time for integer alphabets. An alternative proof of the fact that the number of maximal \(\alpha \) -gapped repeats in a word of length \(n\)  is \({\mathcal {O}}(\alpha n)\)  was given in the very recent [3]}; however, compared to the respective paper, we give a more direct proof of the \({\mathcal {O}}(\alpha n)\)  upper bound as well as a concrete evaluation of the constant hidden by the \({\mathcal {O}}\) -denotation. In [3]}, [5]} algorithms producing all the maximal \(\alpha \) -gapped repeats of a word were given; in the light of the upper bound \({\mathcal {O}}(\alpha n)\)  on the number of maximal \(\alpha \) -gapped repeats that may occur in a word of length \(n\) , it follows that these algorithms work in \({\mathcal {O}}(\alpha n)\)  time, but only for constant alphabets. Extending the approach in [6]}, we show here that, in fact, such algorithms can be also designed for integer alphabets; our algorithm requires a deeper analysis than the one developed in [6]} for finding the longest \(\alpha \) -gapped repeat, and uses essentially different techniques and data structures than the ones in [3]}, [5]}.
