Abstract. We consider two closely related problems of text indexing in a sublinear working space. The first problem is the sparse suffix tree construction, where a text [Formula: see text] is given in read-only memory, along with a set of suffixes [Formula: see text], and the goal is to construct the compressed trie of all these suffixes ordered lexicographically, using only [Formula: see text] words of space. The second problem is the longest common extension problem, where again a text [Formula: see text] of length [Formula: see text] is given in read-only memory with some trade-off parameter [Formula: see text], and the goal is to construct a data structure that uses [Formula: see text] words of space and can compute for any pair of suffixes their longest common prefix length as fast as possible as a function of [Formula: see text] ([Formula: see text] time for a randomized Las Vegas data structure or [Formula: see text] time for a deterministic data structure). We show how to use ideas based on the locally consistent parsing technique, that were introduced by Sahinalp and Vishkin [ Proceedings of the 26 th Annual ACM Symposium on Theory of Computing, 1994, pp. 300–309 ], in some nontrivial ways in order to improve the known results for the above problems under the space constraints. We introduce the first almost-linear, [Formula: see text], deterministic construction for both problems, where all previous algorithms take at least [Formula: see text] time. We also introduce the first linear-time Las Vegas algorithms for both problems, achieving [Formula: see text] construction time with high probability. This is an improvement over the last result of Gawrychowski and Kociumaka [ Proceedings of the 28 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 425–439 ], which obtained [Formula: see text] time for the Monte Carlo algorithm and [Formula: see text] time with high probability for the Las Vegas algorithm.

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, where a text S is given in read-only memory, along with a set of suffixes B, and the goal is to construct the compressed trie of all these suffixes ordered lexicographically, using only (|B|) words of space. The second problem is the Longest Common Extension (LCE) problem, where again a text S of length n is given in read-only memory with some parameter 1 ≤ τ n, and the goal is to construct a data structure that uses words of space and can compute for any pair of suffixes their longest common prefix length. We show how to use ideas based on the Locally Consistent Parsing technique, that were introduced by Sahinalp and Vishkin [44], in some nontrivial ways in order to improve the known results for the above problems. We introduce new Las-Vegas and deterministic algorithms for both problems. For the randomized algorithms, we introduce the first Las-Vegas SST construction algorithm that takes (n) time. This is an improvement over the last result of Gawrychowski and Kociumaka [22] who obtained (n) time for Monte Carlo algorithm, and time with hight probability for Las-Vegas algorithm. In addition, we introduce a randomized Las-Vegas construction for a data structure that uses words of space, can be constructed in linear time with high probability and answers LCE queries in (τ) time. For the deterministic algorithms, we introduce an SST construction algorithm that takes time (for |B| = Ω(log n)). This is the first almost linear time, (n · polylog n), deterministic SST construction algorithm, where all previous algorithms take at least time. For the LCE problem, we introduce a data structure that uses words of space and answers LCE queries in time, with (n log τ) construction time (for ). This data structure improves both query time and construction time upon the results of Tanimura et al. [47].