Locally Consistent Parsing for Text Indexing in Small Space

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 O(|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 MATH HERE 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 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. For the randomized algorithms, 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 22 who obtained O(n) time for Monte Carlo algorithm, and MATH HERE time with hight probability for Las-Vegas algorithm. In addition, we introduce a randomized Las-Vegas construction for a data structure that uses MATH HERE words of space, can be constructed in linear time with high probability and answers LCE queries in O(τ) time. For the deterministic algorithms, we introduce an SST construction algorithm that takes MATH HERE time (for |B| = Ω(log n)). This is the first almost linear time, O(n · polylog n), deterministic SST construction algorithm, where all previous algorithms take at least MATH HERE time. For the LCE problem, we introduce a data structure that uses MATH HERE words of space and answers LCE queries in MATH HERE time, with O(n log τ) construction time MATH HERE. This data structure improves both query time and construction time upon the results of Tanimura et al. 47.