Weighted Ancestors in Suffix Trees Revisited

Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi +1

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\mathop{\math…