New algorithms for binary jumbled pattern matching

DOI10.1016/J.IPL.2013.04.013zbMATH Open1284.68698arXiv1210.6176OpenAlexW2023986152MaRDI QIDQ2444765FDOQ2444765

Authors: Emanuele Giaquinta, Szymon Grabowski 

Publication date: 11 April 2014

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• Dynamic ordered sets with exponential search trees
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Scaled and permuted string matching
• Indexing permutations for binary strings
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• On prefix normal words and prefix normal forms
• On infinite prefix normal words
• On approximate jumbled pattern matching in strings
• 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)