2012/07/04 by Philip Bille, Bille, Philip, Inge Li Gørtz +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.1135
7 pages, submitted
arxiv created 2012/07/04 · openalex publication_date 2012/07/04 · arxiv updated 2012/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 construction time. Breaking the naive bound of Ω(nb) time for this problem has occupied many algorithmic researchers since a different structure, the (evenly spaced) sparse suffix tree, was introduced by Kärkkäinen and Ukkonen in 1996. While in the evenly spaced sparse suffix tree the suffixes considered must be evenly spaced in T, here there is no constraint on the locations of the suffixes. We show that the sparse suffix tree can be constructed in O(nlog2b) time. To achieve this we develop a technique, which may be of independent interest, that allows to efficiently answer b longest common prefix queries on suffixes of T, using only O(b) space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Furthermore, additional tradeoffs between the space usage and the construction time are given.