algorithm - 如何在线性时间内构建后缀树？

Question

要构建后缀树，在最坏的情况下，如果字符串的所有字母都不同，那么复杂度将类似于

n + (n-1) + (n-2) ... 1 = n*(n+1)/2

这是 O(n^2)。

但是根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要 O(n) 时间。我在这里缺少什么？

Answer 1

您对为什么算法应该是 Θ(n²) 的直觉很好，但大多数后缀树的设计方式都消除了这种时间复杂度的需要。直觉上，您似乎需要 Θ(n²) 个不同的节点来保存所有不同的后缀，因为您需要 n + (n - 1) + ... + 1 个不同的节点.但是，后缀树通常设计为后缀中的每个字符没有一个节点。相反，每条边通常都标有一系列字符，这些字符是原始字符串的子字符串。看起来您仍然需要 Θ(n²) 时间来构建这棵树，因为您必须将子字符串复制到这些边上，但通常这可以通过一个可爱的技巧来避免 -由于所有边都标有输入的子串字符串，因此可以用开始和结束位置来标记边，这意味着可以在 O(1) 时间内构造跨越 Θ(n) 个字符的边，并使用 O (1) 空间。

也就是说，构建后缀树仍然很难做到。维基百科中引用的 Θ(n) 算法并不容易。发现在线性时间内工作的第一个算法是 Ukkonen's Algorithm ，这通常在字符串算法教科书中描述(例如 Algorithms on Strings, Trees, and Sequences) 。原始论文在维基百科中有链接。更现代的方法是首先构建一个 suffix array 并使用它来构建后缀树。

希望这对您有所帮助!