Publications

Stats

View publication

Title Counting on General Run-Length Grammars
Authors Gonzalo Navarro, Alejandro Pacheco
Publication date 2025
Abstract We introduce a data structure for counting pattern occurrences in texts compressed with any run-length context-free grammar. Our structure uses space proportional to the grammar size and counts the occurrences of a pattern of length m in a text of length n in time O(mlog^{2+e} n), for any constant e > 0 chosen at indexing time. This is the first solution to an open problem posed by Christiansen et al. [ACM TALG 2020] and enhances our abilities for computation over compressed data; we give an example application.
Pages 3:1-3:17
Conference name Annual Symposium on Combinatorial Pattern Matching
Publisher Springer-Verlag (Berlin/Heidelberg, Germany)
Reference URL View reference page