Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching

We show how, given a straight-line program with $g$ rules for a binary string $B$ of length $n$, in $O(g^{2\mathrm{/}3}{n}^{4\mathrm{/}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.