要构建后缀树，在最坏的情况下，如果字符串的所有字母都不同，那么复杂度将类似于
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
这是O（n ^ 2）。
然而，根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要 O(n) 时间。我在这里想念什么？
问问题
13146 次
1 回答
42
您对为什么算法应该是 Θ(n 2 ) 的直觉是一个很好的直觉，但是大多数后缀树的设计方式都消除了对这种时间复杂度的需求。直观地说，您似乎需要 Θ(n 2 ) 不同的节点来保存所有不同的后缀，因为您需要 n + (n - 1) + ... + 1 个不同的节点。然而，后缀树通常被设计成后缀中的每个字符没有一个节点。相反，每条边通常都标有一系列字符，这些字符是原始字符串的子字符串。看起来你仍然需要 Θ(n 2) 是时候构造这棵树了，因为您必须将子字符串复制到这些边缘，但通常可以通过一个可爱的技巧来避免这种情况 - 因为所有边缘都标有作为输入子字符串的字符串，边缘可以改为标有开始和结束位置，这意味着可以在 O(1) 时间并使用 O(1) 空间构建跨越 Θ(n) 个字符的边。
也就是说，构建后缀树仍然很难。维基百科中引用的 Θ(n) 算法并不容易。最早发现在线性时间内工作的算法之一是Ukkonen 算法，它通常在字符串算法的教科书中进行描述（例如字符串、树和序列的算法）。原始论文链接在 Wikipedia 中。更现代的方法首先构建一个后缀数组，然后使用它来构建后缀树。
希望这可以帮助！
于 2011-09-17T02:12:45.770 回答