Our techniques can be extended to show that the number of maximal \(\alpha \) -gapped palindromes in a word of length \(n\)  is upper bounded by \(28\alpha n + 7n\) ; they can be found in \({\mathcal {O}}(\alpha n)\)  time. As there are words of length \(n\)  that contain \(\Theta (\alpha n)\)  maximal \(\alpha \) -gapped repeats or palindromes (see [1]}), it follows that the bounds on the number of maximal \(\alpha \) -gapped repeats or palindromes we obtained are asymptotically tight, and that we cannot hope for algorithms finding all \(\alpha \) -gapped repeats or palindromes faster in the worst case.
