> Detailanzeige

Crochemore, Maxime [VerfasserIn]; Iliopoulos, Costas S. [VerfasserIn]; Radoszewski, Jakub [VerfasserIn]; Rytter, Wojciech [VerfasserIn]; Straszyński, Juliusz [VerfasserIn]; Waleń, Tomasz [VerfasserIn]; Zuba, Wiktor [VerfasserIn] ; Maxime Crochemore and Costas S. Iliopoulos and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszyński and Tomasz Waleń and Wiktor Zuba [MitwirkendeR]

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

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel; Sonstige Veröffentlichung; Elektronischer Konferenzbericht
  • Titel: Linear-Time Computation of Shortest Covers of All Rotations of a String
  • Beteiligte: Crochemore, Maxime [VerfasserIn]; Iliopoulos, Costas S. [VerfasserIn]; Radoszewski, Jakub [VerfasserIn]; Rytter, Wojciech [VerfasserIn]; Straszyński, Juliusz [VerfasserIn]; Waleń, Tomasz [VerfasserIn]; Zuba, Wiktor [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.CPM.2022.22
  • Schlagwörter: run ; quasiperiod ; cover ; cyclic rotation ; seed
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang