Cover Image

Compressed Dictionary Matching on Run-Length Encoded Strings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bille, Philip, Gørtz, Inge Li, Puglisi, Simon J., Tarnow, Simon R.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

Improved Extended Regular Expression Matching
by: Bille, Philip, et al.
Published: (2025)

Fast Practical Compression of Deterministic Finite Automata
by: Bille, Philip, et al.
Published: (2023)

String Indexing for Top-$k$ Close Consecutive Occurrences
by: Bille, Philip, et al.
Published: (2020)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
by: Bille, Philip, et al.
Published: (2024)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Longest Unbordered Factors on Run-Length Encoded Strings
by: Sekizaki, Shoma, et al.
Published: (2025)

Differentially Private Substring and Document Counting with Near-Optimal Error
by: Bernardini, Giulia, et al.
Published: (2024)

Pattern Discovery in Colored Strings
by: Lipták, Zsuzsanna, et al.
Published: (2020)

An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
by: Sanaullah, Ahsan, et al.
Published: (2025)

Sensitivity of Repetitiveness Measures to String Reversal
by: Bannai, Hideo, et al.
Published: (2026)

Optimal-Time Mapping in Run-Length Compressed PBWT
by: Bonizzoni, Paola, et al.
Published: (2026)

Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
by: Mikkelstrup, Christian Møller, et al.
Published: (2026)

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Suffix sorting via matching statistics
by: Lipták, Zsuzsanna, et al.
Published: (2022)

Improved Circular Dictionary Matching
by: Cotumaccio, Nicola
Published: (2025)

Pattern Masking for Dictionary Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

Counting on General Run-Length Grammars
by: Navarro, Gonzalo, et al.
Published: (2024)

How many users have been here for a long time? Efficient solutions for counting long aggregated visits
by: Afshani, Peyman, et al.
Published: (2026)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

Size-constrained Weighted Ancestors with Applications
by: Bille, Philip, et al.
Published: (2023)

Toward Greener Matrix Operations by Lossless Compressed Formats
by: Tosoni, Francesco, et al.
Published: (2024)

Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
by: Domingues, Gabriel Marques
Published: (2026)

Algorithms for Parameterized String Matching with Mismatches
by: Saha, Apurba, et al.
Published: (2024)

Greedy Dynamic Matching
by: Arnosti, Nick, et al.
Published: (2025)

Height-bounded Lempel-Ziv encodings
by: Bannai, Hideo, et al.
Published: (2024)

Online String Attractors
by: Whittington, Philip
Published: (2024)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Searching 2D-Strings for Matching Frames
by: Boneh, Itai, et al.
Published: (2023)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
by: Dehghani, Hossein, et al.
Published: (2022)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
by: Konstantinovsky, Thomas, et al.
Published: (2026)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

String Matching with a Dynamic Pattern
by: Monteiro, Bruno, et al.
Published: (2025)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
by: Duyster, Anouk, et al.
Published: (2026)