Skip to Main content Skip to Navigation
Journal articles

Number of occurrences of powers in strings

Abstract : We show a Theta(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 Theta(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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00693448
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 10:12:40 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:57 AM

File

Number_of_occurrences_of_power...
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Szilard Zsolt Fazekas, Costas S. Iliopoulos, Inuka Jayasekera. Number of occurrences of powers in strings. International Journal of Foundations of Computer Science, World Scientific Publishing, 2010, 21 (4), pp.535--547. ⟨10.1142/S0129054110007416⟩. ⟨hal-00693448⟩

Share

Metrics

Record views

587

Files downloads

503