 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [17 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00693448
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 10:12:40 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:19 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:57 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 10:12:40 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:19 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:57 AM
File
Number_of_occurrences_of_power...
Files produced by the author(s)