New algorithms for binary jumbled pattern matching

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/{\log }^{2}n)$ (with O(n) space and O(1) query time) and $O(r^2\log r)$ (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\log k+n/k)$ complexity to build the index, $O(\log k)$ query time, and uses $O(n/k+|L|)$ space, where $k$ is a parameter. The second result is an $O(n^2{\log }^{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.

Cited by in corpus (12)

• On Prefix Normal Words and Prefix Normal Forms
• Binary Jumbled Pattern Matching via All-Pairs Shortest Paths
• Algorithms for Computing Abelian Periods of Words
• Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• On Combinatorial Generation of Prefix Normal Words
• Normal, Abby Normal, Prefix Normal
• On Infinite Prefix Normal Words
• Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching
• On the Parikh-de-Bruijn grid
• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
• On Hardness of Jumbled Indexing