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 |
|