r*-indexing

Let $T[\mathrm{1..}n]$ be a text over an alphabet of size $\sigma \in \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n)$, let $r^{\ast }$ 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^{\ast }\log (n\mathrm{/}{r}^{\ast })+z\log n)$ bits such that, given a pattern $P[\mathrm{1..}m]$, we can report the locations of the $\mathrm{o}\mathrm{c}\mathrm{c}$ occurrences of $P$ in $T$ in $O(m\log n+\mathrm{o}\mathrm{c}\mathrm{c}{\log }^{\epsilon }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 }^{\epsilon }n)$ time.