Near-Optimal Search Time in $δ$-Optimal Space, and Vice Versa

Two recent lower bounds on the compressibility of repetitive sequences, $δ\le γ$, have received much attention. It has been shown that a length-$n$ string $S$ over an alphabet of size $σ$ can be represented within the optimal $O(δ\log\tfrac{n\log σ}{δ\log n})$ space, and further, that within that space one can find all the $occ$ occurrences in $S$ of any length-$m$ pattern in time $O(m\log n + occ \log^εn)$ for any constant $ε>0$. Instead, the near-optimal search time $O(m+({occ+1})\log^εn)$ has been achieved only within $O(γ\log\frac{n}γ)$ space. Both results are based on considerably different locally consistent parsing techniques. The question of whether the better search time could be supported within the $δ$-optimal space remained open. In this paper, we prove that both techniques can indeed be combined to obtain the best of both worlds: $O(m+({occ+1})\log^εn)$ search time within $O(δ\log\tfrac{n\log σ}{δ\log n})$ space. Moreover, the number of occurrences can be computed in $O(m+\log^{2+ε}n)$ time within $O(δ\log\tfrac{n\log σ}{δ\log n})$ space. We also show that an extra sublogarithmic factor on top of this space enables optimal $O(m+occ)$ search time, whereas an extra logarithmic factor enables optimal $O(m)$ counting time.