Fast and simple jumbled indexing for binary run-length encoded strings

DOI10.4230/LIPICS.CPM.2017.19MaRDI QIDQ5110883zbMATH OpenOpenAlexFDO

Authors Luís Felipe Ignácio Cunha, Simone Dantas, Travis Gagie, Roland Wittler, Luis Antonio B. Kowada, Jens Stoye

Publication date 25 May 2020

Full work available at URL https://arxiv.org/abs/1702.01280

zbMATH Keywords

indexingjumbled pattern matchingrun-length encodingstring algorithms

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Abstract: 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+h{o}^{2}logho)$ time, where $n$ is the length and $ho$ is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in $O(n+h{o}^2)$ time. In this paper we propose a new and very simple algorithm that also runs in $O(n+h{o}^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.

Recommendations

• Binary jumbled string matching for highly run-length compressible texts
• New algorithms for binary jumbled pattern matching
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings

Cited in

(11)

• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• New algorithms for binary jumbled pattern matching
• Binary jumbled string matching for highly run-length compressible texts
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• An Opportunistic Text Indexing Structure Based on Run Length Encoding
• Indexing permutations for binary strings
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• On infinite prefix normal words
• Bubble-flip -- a new generation algorithm for prefix normal words
• Binary jumbled pattern matching on trees and tree-like structures

This page was built for publication: Fast and simple jumbled indexing for binary run-length encoded strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110883)