# Binary Jumbled Pattern Matching via All-Pairs Shortest Paths

Preprint · Danny Hermelin, Gad M. Landau, Yuri Rabinovich, Oren Weimann

- Archive id: arxiv:1401.2065
- Published: 2014-01-09
- arXiv: https://arxiv.org/abs/1401.2065
- Source URL: https://arxiv.org/abs/1401.2065
- PDF: https://arxiv.org/pdf/1401.2065
- Provenance: arxiv

## Abstract

In binary jumbled pattern matching we wish to preprocess a binary string $S$ in order to answer queries $(i,j)$ which ask for a substring of $S$ that is of size $i$ and has exactly $j$ 1-bits. The problem naturally generalizes to node-labeled trees and graphs by replacing "substring" with "connected subgraph". In this paper, we give an ${n^2}/{2^{Ω(\\log n/\\log \\log n)^{1/2}}}$ time solution for both strings and trees. This odd-looking time complexity improves the state of the art $O(n^2/\\log^2 n)$ solutions by more than any poly-logarithmic factor. It originates from the recent seminal algorithm of Williams for min-plus matrix multiplication. We obtain the result by giving a black box reduction from trees to strings. This is then combined with a reduction from strings to min-plus matrix multiplications.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.