Faster run-length compressed suffix arrays.
Nathaniel K Brown, Travis Gagie, Giovanni Manzini, Gonzalo Navarro, Marinella Sciortino · PubMed · 2025
time, without increasing its asymptotic space bound. Our key idea is applying a result by Nishimoto and Tabei (ICALP 2021) and then replacing rank queries on sparse bitvectors by a constant number of select queries. We also review two-level indexing and discuss how our faster RLCSA may be useful in improving it. Finally, we briefly discuss how two-level indexing may speed up a recent heuristic for finding maximal exact matches of a pattern with respect to an indexed text.