Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyMechanical Proving with Walnut for Squares and Cubes in Partial Words
| cris.lastimport.scopus | 2024-02-12T20:54:25Z |
| dc.abstract.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. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Czechy |
| dc.conference.datefinish | 2022-06-29 |
| dc.conference.datestart | 2022-06-27 |
| dc.conference.place | Praga |
| dc.conference.series | Combinatorial Pattern Matching |
| dc.conference.series | Combinatorial Pattern Matching |
| dc.conference.seriesshortcut | CPM |
| dc.conference.shortcut | CPM 2022 |
| dc.conference.weblink | https://www.stringology.org/event/CPM2022/ |
| dc.contributor.author | Zuba, Wiktor |
| dc.contributor.author | Waleń, Tomasz |
| dc.contributor.author | Straszyński, Juliusz |
| dc.contributor.author | Rytter, Wojciech |
| dc.contributor.author | Radoszewski, Jakub |
| dc.contributor.author | Iliopoulos, Costas S. |
| dc.contributor.author | Crochemore, Maxime |
| dc.date.accessioned | 2024-01-25T11:26:03Z |
| dc.date.available | 2024-01-25T11:26:03Z |
| dc.date.issued | 2022 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.identifier.doi | 10.4230/LIPICS.CPM.2022.5 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/112193 |
| dc.identifier.weblink | https://drops.dagstuhl.de/opus/volltexte/2022/16132/ |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 5: 1-11 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | Partial words |
| dc.subject.en | squares |
| dc.subject.en | antisquares |
| dc.subject.en | cubes |
| dc.subject.en | Walnut |
| dc.title | Mechanical Proving with Walnut for Squares and Cubes in Partial Words |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |