Given a pattern $P$ and a text $T$, both strings over a binary alphabet, thebinary jumbled string matching problem consists in telling whether anypermutation of $P$ occurs in $T$. The indexed version of this problem, i.e.,preprocessing a string to efficiently answer such permutation queries, is hardand has been studied in the last few years. Currently the best bounds for thisproblem are $O(n^2/log^2 n)$ (with O(n) space and O(1) query time) and$O(r^2log r)$ (with O(|L|) space and $O(log|L|)$ query time), where $r$ isthe length of the run-length encoding of $T$ and $|L| = O(n)$ is the size ofthe index. In this paper we present new results for this problem. Our firstresult is an alternative construction of the index by Badkobeh et al. thatobtains a trade-off between the space and the time complexity. It has$O(r^2log k + n/k)$ complexity to build the index, $O(log k)$ query time, anduses $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 onword-level parallelism where $w$ is the word size in bits.
展开▼
机译：给定模式$ p $和text $ t $，两个字母在二进制字母表中，它的混乱字符串匹配问题在于讲述$ p $的umermutge是否以$ t $出现。此问题的索引版本，即预处理字符串，以有效地回答此类排列查询，但已在过去几年中进行了Hardand。目前这个问题的最佳界限是$ o（n ^ 2 / log ^ 2 n）$（使用o（n）空间和o（1）查询时间）和$ o（r ^ 2 log r）$（带o（| l |）空间和$ O（ log | l |）$查询时间），其中$ r $是$ t $和$的运行长度编码的长度| l | = o（n）$是索引的大小。在本文中，我们为此问题提出了新的结果。我们的Firstresult是Badkobeh等人的替代建设。在空间和时间复杂之间的替代方案。它有$ o（r ^ 2 log k + n / k）$复杂性来构建索引，$ o（ log k）$查询时间，anduses $ o（n / k + | l |）$空间，在哪里$ k $是一个参数。第二个结果是$ o（n ^ 2 log ^ 2 w / w）$算法（使用o（n）空间和o（1）查询时间），基于worw级并行性，其中$ w $是字大小在比特。
展开▼
