2026-07-24T00:02:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8261 2024-03-06T10:41:49Z ddc:004 open_access

Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings Fujishige, Yuta Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki maximal repetitions,run length encoding We consider the problem of computing all maximal repetitions contained in a string that is given in run-length encoding. Given a run-length encoding of a string, we show that the maximum number of maximal repetitions contained in the string is at most m+k-1, where m is the size of the run-length encoding, and k is the number of run-length factors whose exponent is at least 2. We also show an algorithm for computing all maximal repetitions in O(m \alpha(m)) time and O(m) space, where \alpha denotes the inverse Ackermann function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuta Fujishige and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.33 urn:nbn:de:0030-drops-82610 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.33 eng https://creativecommons.org/licenses/by/3.0/legalcode