Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String

Uproszczony widok
dc.abstract.enCyclic versions of covers and roots of a string are considered in this paper. A prefix V of a string S is a cyclic root of S if S is a concatenation of cyclic rotations of V. A prefix V of S is a cyclic cover of S if the occurrences of the cyclic rotations of V cover all positions of S. We present (n)-time algorithms computing all cyclic roots (using number-theoretic tools) and all cyclic covers (using tools related to seeds) of a length-n string over an integer alphabet. Our results improve upon (n log log n) and (n log n) time complexities of recent algorithms of Grossi et al. (WALCOM 2023) for the respective problems and provide novel approaches to the problems. As a by-product, we obtain an optimal data structure for Internal Circular Pattern Matching queries that generalize Internal Pattern Matching and Cyclic Equivalence queries of Kociumaka et al. (SODA 2015).
dc.affiliationUniwersytet Warszawski
dc.conference.countryFrancja
dc.conference.datefinish2023-06-28
dc.conference.datestart2023-06-26
dc.conference.placeMarne-la-Vallée
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesshortcutCPM
dc.conference.shortcutCPM 2023
dc.conference.weblinkhttps://cpm2023.u-pem.fr/
dc.contributor.authorZuba, Wiktor
dc.contributor.authorWaleń, Tomasz
dc.contributor.authorRytter, Wojciech
dc.contributor.authorRadoszewski, Jakub
dc.contributor.authorKociumaka, Tomasz
dc.contributor.authorIliopoulos, Costas S.
dc.date.accessioned2024-01-25T05:11:32Z
dc.date.available2024-01-25T05:11:32Z
dc.date.copyright2023-06-21
dc.date.issued2023
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.CPM.2023.15
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111278
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2023/17969/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages15:1-15
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.encyclic cover
dc.subject.encyclic root
dc.subject.encircular pattern matching
dc.subject.eninternal pattern matching
dc.titleLinear-Time Computation of Cyclic Roots and Cyclic Covers of a String
dc.typeJournalArticle
dspace.entity.typePublication