Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching

2012/10/31 by Travis Gagie, Gagie, Travis
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1210.8386

openalex publication_date 2012/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Application of Lempel–Ziv factorization to the approximation of grammar-based compression

Related

• Fast and Simple Jumbled Indexing for Binary RLE Strings
• Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
• Linear-Space Substring Range Counting over Polylogarithmic Alphabets
• Binary Jumbled Pattern Matching via All-Pairs Shortest Paths