Weighted ancestors in suffix trees. (English) Zbl 1425.68087

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 455-466 (2014).
Summary: The classical, ubiquitous, predecessor problem is to construct a data structure for a set of integers that supports fast predecessor queries. Its generalisation to weighted trees, a.k.a. the weighted ancestor problem, has been extensively explored and successfully reduced to the predecessor problem. It is known that any data structure solution for the weighted ancestor problem that occupies \(O(n \operatorname{polylog}(n))\) space must have \(\Omega (\log \log n)\) query time, if the weights are drawn from a polynomially bounded universe. Perhaps the most important and frequent application of the weighted ancestors problem is for suffix trees. It has been a long-standing open question whether the weighted ancestors problem has better bounds for suffix trees. We answer this question positively: we show that a suffix tree built for a text \(w[1..n]\) can be preprocessed using \(O(n)\) extra space, so that queries can be answered in \(O(1)\) time. Thus we improve the running times of several applications. Our improvement is based on a number of data structure tools and a periodicity-based insight into the combinatorial structure of a suffix tree.
For the entire collection see [Zbl 1295.68031].


68P05 Data structures
Full Text: DOI arXiv Link