Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty

Linear-Time Computation of Shortest Covers of All Rotations of a String

Autor
Zuba, Wiktor
Waleń, Tomasz
Straszyński, Juliusz
Rytter, Wojciech
Radoszewski, Jakub
Iliopoulos, Costas S.
Crochemore, Maxime
Data publikacji
2022
Abstrakt (EN)

We show that lengths of shortest covers of all rotations of a length-n string over an integer alphabet can be computed in (n) time in the word-RAM model, thus improving an (n log n)-time algorithm from Crochemore et al. (Theor. Comput. Sci., 2021). Similarly as Crochemore et al., we use a relation of covers of rotations of a string S to seeds and squares in S³. The crucial parameter of a string S is the number ξ(S) of primitive covers of all rotations of S. We show first that the time complexity of the algorithm from Crochemore et al. can be slightly improved which results in time complexity Θ(ξ(S)). However, we also show that in the worst case ξ(S) is Ω(|S|log |S|). This is the main difficulty in obtaining a linear time algorithm. We overcome it and obtain yet another application of runs in strings.

Słowa kluczowe EN
cover
quasiperiod
cyclic rotation
seed
run
Dyscyplina PBN
informatyka
Strony od-do
22:1--22:15
Licencja otwartego dostępu
Dostęp zamknięty