New simple efficient algorithms computing powers and runs in strings

Abstract : Run in a string Square in a string Cube in a string Dictionary of Basic Factors a b s t r a c t Three new simple O(n log n) time algorithms related to repeating factors are presented in the paper. The first two algorithms employ only a basic textual data structure called the Dictionary of Basic Factors. Despite their simplicity these algorithms not only detect existence of powers (in particular, squares) in a string but also find all primitively rooted cubes (as well as higher powers) and all cubic runs. Our third O(n log n) time algorithm computes all runs and is probably the simplest known efficient algorithm for this problem. It uses additionally the Longest Common Extension function, however, due to relaxed running time constraints, a simple O(n log n) time implementation can be used. At the cost of logarithmic factor (in time complexity) we obtain novel algorithmic solutions for several classical string problems which are much simpler than (usually quite sophisticated) linear time algorithms.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806287
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 8, 2018 - 12:12:44 PM
Last modification on : Saturday, June 9, 2018 - 1:13:20 AM
Long-term archiving on : Sunday, September 9, 2018 - 12:39:49 PM

File

simplesq_psc_proceedings.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, C.S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, et al.. New simple efficient algorithms computing powers and runs in strings. Discrete Applied Mathematics, Elsevier, 2014, 163, pp.258-267. ⟨10.1016/j.dam.2013.05.009⟩. ⟨hal-01806287⟩

Share

Metrics

Record views

31

Files downloads

128