[1..n']$, so that $R (a, j)$ if and only if character $a$ appears in block $s' [j]$. Rather than storing $R$ explicitly, we store only its succinct index [@BHMR07 Theorem 3.2], which uses Ferragina and Venturini’s data structure and takes ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}}$ more bits, where $p \leq \min (n, n' \sigma)$ is the number of pairs in $R$. If $\sigma = {\ensuremath{\mathcal{O}\left( {1} \right)}}$ then ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}} = {\ensuremath{\mathcal{O}\left( {n'} \right)}} = o (n)$; otherwise, ${\ensuremath{\mathcal{O}\left( {p \lg \sigma / \lg \lg \sigma} \right)}} = {\ensuremath{\mathcal{O}\left( {n \lg \sigma / \lg \lg \lg n} \right)}} = o (n) \lg \sigma$. This succinct index allows us to find the number of blocks in $s' [1..j]$ containing $a$’s in ${\ensuremath{\mathcal{O}\left( {(\lg \lg \sigma)^2 \lg \lg \lg \sigma} \right)}}$ time, and to find the $r$th block containing $a$’s in time ${\ensuremath{\mathcal{O}\left( {\lg \lg \sigma \lg \lg \lg \sigma} \right)}}$.

For each of the $p$ pairs $(a,j)$ in $R$, we store the number of times $a$ appears in $S'[j]$. Assume we store these numbers $x$ as $x+1$ bits $1^x0$ and concatenate them all, row-wise, into a bitmap $P$ with $n$ 