Let T 1. . n be a text over an alphabet of size σ 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^* (n / r^*) + z n) bits such that, given a pattern P 1. . m, we can report the locations of the occ occurrences of P in T in O (m n + occ ^ε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 ^εn) time.
Travis Gagie (Mon,) studied this question.