Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
From MaRDI portal
Publication:2006779
DOI10.1016/j.tcs.2020.07.035zbMath1460.68135arXiv2003.03222MaRDI QIDQ2006779
Joe Sawada, Gabriele Fici, Péter Burcsi, Zsuzsanna Lipták, Rajeev Raman
Publication date: 12 October 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.03222
jumbled pattern matching; binary languages; prefix normal words; combinatorial Gray code; combinatorial generation
Related Items
On infinite prefix normal words, Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions, Weighted prefix normal words: mind the gap
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Sub-quadratic time and linear space data structures for permutation matching in binary strings
- Efficient oracles for generating binary bubble languages
- Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
- Efficient indexes for jumbled pattern matching with constant-sized alphabet
- Binary bubble languages and cool-lex order
- On approximate jumbled pattern matching in strings
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- Binary jumbled pattern matching on trees and tree-like structures
- Leaf realization problem, caterpillar graphs and prefix normal words
- The asymptotic number of prefix normal words
- Approximating the maximum consecutive subsums of a sequence
- New algorithms for binary jumbled pattern matching
- ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
- Clustered Integer 3SUM via Additive Combinatorics
- On the relationship between histogram indexing and block-mass indexing
- Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings
- A Lower Bound for Jumbled Indexing
- On Combinatorial Generation of Prefix Normal Words
- On Hardness of Jumbled Indexing
- On Prefix Normal Words
- On infinite prefix normal words
- Bubble-flip -- a new generation algorithm for prefix normal words
