2026-07-24T12:06:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7341 2024-03-06T10:40:08Z ddc:004 open_access

Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings Cunha, Luís Dantas, Simone Gagie, Travis Wittler, Roland Kowada, Luis Stoye, Jens string algorithms indexing jumbled pattern matching run-length encoding Important papers have appeared recently on the problem of indexing binary strings for jumbled pattern matching, and further lowering the time bounds in terms of the input size would now be a breakthrough with broad implications. We can still make progress on the problem, however, by considering other natural parameters. Badkobeh et al. (IPL, 2013) and Amir et al. (TCS, 2016) gave algorithms that index a binary string in O(n + r^2 log r) time, where n is the length and r is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in O(n + r^2) time. In this paper we propose a new and very simple algorithm that also runs in O(n + r^2) time and can be extended either so that the index returns the position of a match (if there is one), or so that the algorithm uses only O(n) bits of space instead of O(n) words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luís Cunha and Simone Dantas and Travis Gagie and Roland Wittler and Luis Kowada and Jens Stoye 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.19 urn:nbn:de:0030-drops-73418 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode