NUMBER OF OCCURRENCES OF POWERS IN STRINGS
Maxime Crochemore, Szilárd Zsolt Fazekas, Costas S. Iliopoulos, Inuka Jayasekera · International Journal of Foundations of Computer Science · 2010
We show a Θ(n log n) bound on the maximal number of occurrences of primitively-rooted k-th powers occurring in a string of length n for any integer k, k ≥ 2. We also show a Θ(n 2 ) bound on the maximal number of primitively-rooted powers with fractional exponent e, 1 < e < 2, occurring in a string of length n. This result holds obviously for their maximal number of occurrences. The first result contrasts with the linear number of occurrences of maximal repetitions of exponent at least 2.