= Solution
Build an <FM-index>: store the <Burrows-Wheeler transform>, cumulative character counts $C$, and a structure supporting fast <rank queries> for $\operatorname{Occ}(c,r)$. Then each step of <backward search> uses two <rank queries> instead of rescanning the last column. A <wavelet tree> or suitably checkpointed counts can supply these queries while keeping memory manageable. The counting cost is proportional to query length times the <rank query> cost, rather than repeatedly scanning the whole <genome>.<Opportunistic Data Structures with Applications by Paolo Ferragina and others>[§2, LF-mapping; §§3.1–3.2, counting and locating occurrences]{ref}
To recover genomic positions, store a sampled <suffix array> and follow the <last-to-first mapping> to a sampled position, adding the number of steps taken. More samples trade storage for faster position recovery. \b[Index character counts and sample positions], rather than storing the quadratic-size full <cyclic rotation> <matrix>.
Back to article page
