New algorithms for binary jumbled pattern matching

DOI10.1016/J.IPL.2013.04.013MaRDI QIDQ2444765zbMATH OpenOpenAlexFDO

Authors Emanuele Giaquinta, Szymon Grabowski

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial problemsstring algorithmsjumbled pattern matchingrun-length encodingword-level parallelismParikh vectors

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: Given a pattern $P$ and a text $T$, both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of $P$ occurs in $T$. The indexed version of this problem, i.e., preprocessing a string to efficiently answer such permutation queries, is hard and has been studied in the last few years. Currently the best bounds for this problem are $O(n^2/lo{g}^{2}n)$ (with O(n) space and O(1) query time) and $O(r^{2}logr)$ (with O(|L|) space and $O(log|L|)$ query time), where $r$ is the length of the run-length encoding of $T$ and $|L|=O(n)$ is the size of the index. In this paper we present new results for this problem. Our first result is an alternative construction of the index by Badkobeh et al. that obtains a trade-off between the space and the time complexity. It has $O(r^{2}logk+n/k)$ complexity to build the index, $O(logk)$ query time, and uses $O(n/k+|L|)$ space, where $k$ is a parameter. The second result is an $O(n^{2}lo{g}^{2}w/w)$ algorithm (with O(n) space and O(1) query time), based on word-level parallelism where $w$ is the word size in bits.

Recommendations

• Fast and simple jumbled indexing for binary run-length encoded strings
• Binary jumbled string matching for highly run-length compressible texts
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Indexing permutations for binary strings

Cites work

• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 1263219 (Why is no real title available?)
• Dynamic ordered sets with exponential search trees
• Indexing permutations for binary strings
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Scaled and permuted string matching
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cited in

(16)

• Bubble-flip -- a new generation algorithm for prefix normal words
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On prefix normal words and prefix normal forms
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• On approximate jumbled pattern matching in strings
• On infinite prefix normal words
• Fast and simple jumbled indexing for binary run-length encoded strings
• Algorithms for computing abelian periods of words
• On hardness of jumbled indexing
• Binary jumbled pattern matching on trees and tree-like structures
• Engineering motif search for large motifs
• Binary jumbled pattern matching on trees and tree-like structures
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Improved online algorithms for jumbled matching
• Algorithms for jumbled pattern matching in strings

This page was built for publication: New algorithms for binary jumbled pattern matching

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