{"ID":2880998,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.12675","arxiv_id":"2508.12675","title":"r*-indexing","abstract":"Let $T [1..n]$ be a text over an alphabet of size $σ\\in \\mathrm{polylog} (n)$, let $r^*$ be the sum of the numbers of runs in the Burrows-Wheeler Transforms of $T$ and its reverse, and let $z$ be the number of phrases in the LZ77 parse of $T$. We show how to store $T$ in $O (r^* \\log (n / r^*) + z \\log n)$ bits such that, given a pattern $P [1..m]$, we can report the locations of the $\\mathrm{occ}$ occurrences of $P$ in $T$ in $O (m \\log n + \\mathrm{occ} \\log^εn)$ time. We can also report the position of the leftmost and rightmost occurrences of $P$ in $T$ in the same space and $O (m \\log^εn)$ time.","short_abstract":"Let $T [1..n]$ be a text over an alphabet of size $σ\\in \\mathrm{polylog} (n)$, let $r^*$ be the sum of the numbers of runs in the Burrows-Wheeler Transforms of $T$ and its reverse, and let $z$ be the number of phrases in the LZ77 parse of $T$. We show how to store $T$ in $O (r^* \\log (n / r^*) + z \\log n)$ bits such th...","url_abs":"https://arxiv.org/abs/2508.12675","url_pdf":"https://arxiv.org/pdf/2508.12675v1","authors":"[\"Travis Gagie\"]","published":"2025-08-18T07:14:02Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}