Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

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

Uproszczony widok
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2022-06-29
dc.conference.datestart2022-06-27
dc.conference.placePraga
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesshortcutCPM
dc.conference.shortcutCPM 2022
dc.conference.weblinkhttps://www.stringology.org/event/CPM2022/
dc.contributor.authorZuba, Wiktor
dc.contributor.authorWaleń, Tomasz
dc.contributor.authorStraszyński, Juliusz
dc.contributor.authorRytter, Wojciech
dc.contributor.authorRadoszewski, Jakub
dc.contributor.authorIliopoulos, Costas S.
dc.contributor.authorCrochemore, Maxime
dc.date.accessioned2024-01-25T05:11:33Z
dc.date.available2024-01-25T05:11:33Z
dc.date.issued2022
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.CPM.2022.22
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111279
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2022/16149/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages22:1--22:15
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.encover
dc.subject.enquasiperiod
dc.subject.encyclic rotation
dc.subject.enseed
dc.subject.enrun
dc.titleLinear-Time Computation of Shortest Covers of All Rotations of a String
dc.typeJournalArticle
dspace.entity.typePublication