Abstract

Two recent lower bounds on the compressibility of repetitive sequences, ???, 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(?lognlog??logn) space, and further, that within that space one can find all the occ occurrences in S of any length-m pattern in time O(mlogn+occlog?n) for any constant ?>0. Instead, the near-optimal search time O(m+(occ+1)log?n) has been achieved only within O(?logn?) 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(?lognlog??logn) space. Moreover, the number of occurrences can be computed in O(m+log2+?n) time within O(?lognlog??logn) 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. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023.