Deterministic sub-linear space LCE data structures with efficient construction

Abstract

Given a string $S$ of $n$ symbols, a longest common extension query $\mathsf{LCE}(i,j)$ asks for the length of the longest common prefix of the $i$th and $j$th suffixes of $S$. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015: 65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and query time. In particular, for a parameter $1\le \tau \le n$, their best deterministic solution is a data structure of size $O(n/\tau )$ which allows LCE queries to be answered in $O(\tau )$ time. However, the construction time for all deterministic versions of their data structure is quadratic in $n$. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of $O(\tau \min \{\log \tau ,\log \frac{n}{\tau }\})$ query time using $O(n/\tau )$ space, but significantly improve the construction time to $O(n\tau )$.

updated title

References in corpus (1)

• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small

Cited by in corpus (1)

• Locally Consistent Parsing for Text Indexing in Small Space