1

我已经用简单的英语阅读了 Ukkonen 的后缀树算法的帖子？. 但目前尚不清楚如何使用该算法获得叶子标签。

在后缀树中，叶子标签是数字 i，使得 S[i..n] 是叶子表示的后缀。如果我想要这样的标签，总复杂度仍然是 O(n) 吗？

怎么做？

4

1 回答 1

1

我找到了解决方案。在每个节点中记录另一个L变量以存储end - start所有祖先的总和。该值指示在特定节点处结束的子字符串的长度，即对于叶子，它是后缀的长度。L每当添加树节点或拆分树节点时都会更新。

那么叶子标签就是n - leaf.L

于 2014-03-20T22:48:22.860 回答