Counting on General Run-Length Grammars
<|reference_start|>Counting on General Run-Length Grammars: 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+\epsilon} n)), for any constant (\epsilon > 0). This closes 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.<|reference_end|>
@article{navarro2024counting,
    title={Counting on General Run-Length Grammars},
    author={Gonzalo Navarro and Alejandro Pacheco},
    journal={arXiv preprint arXiv:2406.00221},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.00221},
    primaryClass={cs.DS}
}