  We revisit the longest common extension (LCE) problem, that is, preprocess a
string $T$ into a compact data structure that supports fast LCE queries. An LCE
query takes a pair $(i,j)$ of indices in $T$ and returns the length of the
longest common prefix of the suffixes of $T$ starting at positions $i$ and $j$.
We study the time-space trade-offs for the problem, that is, the space used for
the data structure vs. the worst-case time for answering an LCE query. Let $n$
be the length of $T$. Given a parameter $\tau$, $1 \leq \tau \leq n$, we show
how to achieve either $O(\infrac{n}{\sqrt{\tau}})$ space and $O(\tau)$ query
time, or $O(\infrac{n}{\tau})$ space and $O(\tau \log({|\LCE(i,j)|}/{\tau}))$
query time, where $|\LCE(i,j)|$ denotes the length of the LCE returned by the
query. These bounds provide the first smooth trade-offs for the LCE problem and
almost match the previously known bounds at the extremes when $\tau=1$ or
$\tau=n$. We apply the result to obtain improved bounds for several
applications where the LCE problem is the computational bottleneck, including
approximate string matching and computing palindromes. We also present an
efficient technique to reduce LCE queries on two strings to one string.
Finally, we give a lower bound on the time-space product for LCE data
structures in the non-uniform cell probe model showing that our second
trade-off is nearly optimal.
