LIPIcs.CPM.2022.22.pdf
- Filesize: 0.84 MB
- 15 pages
Document
Linear-Time Computation of Shortest Covers of All Rotations of a String
Authors
Maxime Crochemore 
,
Costas S. Iliopoulos ,
Jakub Radoszewski ,
Wojciech Rytter ,
Juliusz Straszyński ,
Tomasz Waleń ,
Wiktor Zuba
-
Part of:
Volume:
33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-22
File
Document Identifiers
Author Details
Cite As Get BibTex
Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Linear-Time Computation of Shortest Covers of All Rotations of a String. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CPM.2022.22
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Pattern matching
Keywords
- cover
- quasiperiod
- cyclic rotation
- seed
- run
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alberto Apostolico, Martin Farach, and Costas S. Iliopoulos. Optimal superprimitivity testing for strings. Information Processing Letters, 39(1):17-20, 1991. URL: https://doi.org/10.1016/0020-0190(91)90056-N.
- Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM Journal on Computing, 46(5):1501-1514, 2017. URL: https://doi.org/10.1137/15M1011032.
- Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi, and Rajeev Raman. Weighted ancestors in suffix trees revisited. In Pawel Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland, volume 191 of LIPIcs, pages 8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CPM.2021.8.
- Dany Breslauer. An on-line string superprimitivity test. Information Processing Letters, 44(6):345-347, 1992. URL: https://doi.org/10.1016/0020-0190(92)90111-8.
- Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. The number of repetitions in 2D-strings. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 32:1-32:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.32.
- Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Extracting powers and periods in a word from its runs structure. Theoretical Computer Science, 521:29-41, 2014. URL: https://doi.org/10.1016/j.tcs.2013.11.018.
- Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Internal quasiperiod queries. In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 60-75. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-59212-7_5.
- Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Shortest covers of all cyclic shifts of a string. Theoretical Computer Science, 866:70-81, 2021. URL: https://doi.org/10.1016/j.tcs.2021.03.011.
- Maxime Crochemore and Wojciech Rytter. Squares, cubes, and time-space efficient string searching. Algorithmica, 13(5):405-425, 1995. URL: https://doi.org/10.1007/BF01190846.
- Patryk Czajka and Jakub Radoszewski. Experimental evaluation of algorithms for computing quasiperiods. Theoretical Computer Science, 854:17-29, 2021. URL: https://doi.org/10.1016/j.tcs.2020.11.033.
- Martin Farach. Optimal suffix tree construction with large alphabets. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pages 137-143. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/SFCS.1997.646102.
- Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109-114, 1965. URL: http://www.jstor.org/stable/2034009.
- Aviezri S. Fraenkel and Jamie Simpson. How many squares can a string contain? Journal of Combinatorial Theory, Series A, 82(1):112-120, 1998. URL: https://doi.org/10.1006/jcta.1997.2843.
- Costas S. Iliopoulos, Dennis W. G. Moore, and William F. Smyth. A characterization of the squares in a Fibonacci string. Theoretical Computer Science, 172(1-2):281-291, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00141-7.
- Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. A linear-time algorithm for seeds computation. ACM Transactions on Algorithms, 16(2):27:1-27:23, 2020. URL: https://doi.org/10.1145/3386369.
- Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Internal pattern matching queries in a text and applications. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532-551. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.36.
- Roman M. Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 596-604. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814634.
- Yin Li and William F. Smyth. Computing the cover array in linear time. Algorithmica, 32(1):95-106, 2002. URL: https://doi.org/10.1007/s00453-001-0062-2.
- Dennis W. G. Moore and William F. Smyth. A correction to "An optimal algorithm to compute all the covers of a string". Information Processing Letters, 54(2):101-103, 1995. URL: https://doi.org/10.1016/0020-0190(94)00235-Q.