Sparse Suffix Tree Construction with Small Space

Philip Bille, Inge Li Gørtz, Tsvi Kopelowitz +2

We consider the problem of constructing a sparse suffix tree (or suffix array) for $b$ suffixes of a given text $T$ of size $n$, using only $O(b)$ words of space during constructio…