  We consider two closely related problems of text indexing in a sub-linear
working space. The first problem is the Sparse Suffix Tree (SST) construction
of a set of suffixes $B$ using only $O(|B|)$ words of space. The second problem
is the Longest Common Extension (LCE) problem, where for some parameter
$1\le\tau\le n$, the goal is to construct a data structure that uses $O(\frac
{n}{\tau})$ words of space and can compute the longest common prefix length of
any pair of suffixes. We show how to use ideas based on the Locally Consistent
Parsing technique, that was introduced by Sahinalp and Vishkin [STOC '94], in
some non-trivial ways in order to improve the known results for the above
problems. We introduce new Las-Vegas and deterministic algorithms for both
problems.
  We introduce the first Las-Vegas SST construction algorithm that takes $O(n)$
time. This is an improvement over the last result of Gawrychowski and Kociumaka
[SODA '17] who obtained $O(n)$ time for Monte-Carlo algorithm, and
$O(n\sqrt{\log |B|})$ time for Las-Vegas algorithm. In addition, we introduce a
randomized Las-Vegas construction for an LCE data structure that can be
constructed in linear time and answers queries in $O(\tau)$ time.
  For the deterministic algorithms, we introduce an SST construction algorithm
that takes $O(n\log \frac{n}{|B|})$ time (for $|B|=\Omega(\log n)$). This is
the first almost linear time, $O(n\cdot poly\log{n})$, deterministic SST
construction algorithm, where all previous algorithms take at least
$\Omega\left(\min\{n|B|,\frac{n^2}{|B|}\}\right)$ time. For the LCE problem, we
introduce a data structure that answers LCE queries in $O(\tau\sqrt{\log^*n})$
time, with $O(n\log\tau)$ construction time (for $\tau=O(\frac{n}{\log n})$).
This data structure improves both query time and construction time upon the
results of Tanimura et al. [CPM '16].
