  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 \leq \tau \leq 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)$.
