Counting on General Run-Length Grammars
Gonzalo Navarro and Alejandro Pacheco
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(m log^(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.