The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known that it requires \Omega(\log\log n) time for queries provided O(n\mathrm{polylog} n) space is available and weights are from [0..n], where n is the number of tree nodes. However, when applied to suffix trees, the problem, surprisingly, admits an O(n)-space solution with constant query time  as was shown by Gawrychowski, Lewenstein, and Nicholson . This variant of the problem can be reformulated as follows: given the suffix tree of a string s, we need a data structure that can locate in the tree any substring s[p..q] of s in O(1) time (as if one descended from the root reading s[p..q] along the way). Unfortunately, the data structure of Gawrychowski et al. has no efficient construction algorithm, which apparently prevents its wide usage . In this paper we resolve this issue  describing a data structure for weighted ancestors in suffix trees with constant query time and a linear construction algorithm. Our solution is based on a novel approach using so-called irreducible LCP values.
The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require \Omega(\log\log n) time for queries provided O(n\mathrm{polylog} n) space is available and weights are from [0..n], where n is the number of tree nodes. However, when applied to suffix trees, the problem, surprisingly, admits an O(n)-space solution with constant query time , as was shown by Gawrychowski, Lewenstein, and Nicholson (Proc. ESA 2014). This variant of the problem can be reformulated as follows: given the suffix tree of a string s, we need a data structure that can locate in the tree any substring s[p..q] of s in O(1) time (as if one descended from the root reading s[p..q] along the way). Unfortunately, the data structure of Gawrychowski et al. has no efficient construction algorithm, limiting its wider usage as an algorithmic tool . In this paper we resolve this issue , describing a data structure for weighted ancestors in suffix trees with constant query time and a linear construction algorithm. Our solution is based on a novel approach using so-called irreducible LCP values.
R
that it requires
to require
A
,
R
.
(Proc. ESA 2014).
R
which apparently prevents its wide usage
limiting its wider usage as an algorithmic tool
A
,