Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching

Abstract

We show how, given a straight-line program with $g$ rules for a binary string $B$ of length $n$, in $O(g^{2/3}{n}^{4/3})$ time we can build a linear-space index such that, given $m$ and $c$, in O(1) time we can determine whether there is a substring of $B$ with length $m$ containing exactly $c$ copies of 1. If we use $O(n\log n)$ space for the index, then we can list all such substrings using $O(m)$ time per substring.

References in corpus (1)

• New algorithms for binary jumbled pattern matching