Near-Optimal Search Time in δ-Optimal Space

Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares

Two recent lower bounds on the compressiblity of repetitive sequences, δ <= γ, have received much attention. It has been shown that a string S[1..n] can be represented within the optimal O(δ log(n/δ)) space, and further, that within that space one can find all the occ occurrences in S of any pattern of length m 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) was achieved only within O(γ log(n/γ)) space. Both results are based on considerably different locally consistent parsing techniques. The question of whether the better search time could be obtained within the δ-optimal space was open. In this paper we prove that both techniques can indeed be combined in order to obtain the best of both worlds, O(m + (occ+1) log^ε n) search time within O(δ log(n/δ)) space.