|
Title |
Near-Optimal Search Time in delta-Optimal Space |
|
Authors |
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares |
|
Publication date |
2022 |
|
Abstract |
Two recent lower bounds on the compressiblity of repetitive sequences, \delta \le \gamma, have received much attention. It has been shown that a string S[1..n] can be represented within the optimal O(\delta log(n/\delta)) 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^\epsilon n) for any constant \epsilon>0. Instead, the near-optimal search time O(m + (occ+1) log^\epsilon n) was achieved only within O(\gamma log(n/\gamma)) 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 \delta-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^\epsilon n) search time within O(\delta log(n/\delta)) space. |
|
Pages |
88-103 |
|
Conference name |
International Symposium of Latin American Theoretical Informatics |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
