Optimality of some algorithms to detect quasiperiodicities

Improving a 1993 algorithm of Apostolico and Ehrenfeucht, independently Iliopoulos and Mouchard in 1999 and Brodal and Pedersen in 2000 provided O(nlog(n)) algorithms to determine all maximal quasiperiodicities of a word of length n. We show here the optimality of this bound providing an infinite family of words w containing O(|w|log|w|) maximal quasiperiodicities. We also show that this bound is not reached for the celebrated family of Fibonacci words.