Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree

Abstract

We present a compact semi-dynamic text index which allows us to find short patterns efficiently. For parameters $k\le q \le \log _\sigma n - \log _\sigma \log _\sigma n$ and alphabet size $\sigma = O(\mathrm {polylog}(n))$, all $occ$ occurrences of a pattern of length at most $q-k+1$ can be obtained in $O(k \times occ + \log _\sigma n)$ time, where $n$ is the length of the text. Adding characters to the end of the text is supported in amortized constant time. Our index requires $(n/k) \log (n/k) + n \log \sigma + o(n)$ bits of space, which is compact (i.e., $O(n \log \sigma )$) when $k = \varTheta (\log _{\sigma } n)$. As a byproduct, we present a succinct van Emde Boas tree which supports insertion, deletion, predecessor, and successor on a dynamic set of integers over the universe $[0, m-1]$ in $O(\log \log m)$ time and requires only $m + o(m)$ bits of space.