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