sia*_*831 5 algorithm big-o suffix-tree time-complexity data-structures
我无法理解构造后缀树的最坏情况时间复杂性是如何线性的 - 特别是当我们需要为可能由重复单个字符组成的字符串构建后缀树时,例如"aaaaa".
即使我要为"aaaaa"构造一个压缩后缀树,我也无法真正压缩任何节点,因为从节点开始的两个边都不能有以相同字符开头的字符串标签.
这将导致高度为5的后缀树,并且在每次插入后缀时,我将需要保持从根到叶的遍历.
这是我接近的方式:后缀:a,aa,aaa,aaaa,aaaaa
创建根节点,创建一个带有'a'的边缘并将其连接到一个新节点,其左边带有"$",并重复此过程直到我们可以aaaaa.
这将导致O(n ^ 2)而不是O(n).我在这里错过了什么？
我同意这些评论，但这里有一些更多细节：
您描述的形成树的过程aaaaa是 O(n)，而不是 O(n^2)。节点和叶子创建是常数时间操作，您执行它们 n==5 次。您对 O(n^2) 的假设似乎基于这样的想法：您将在每一步中从根遍历到叶子，但没有必要这样做；例如，在 Ukkonen 算法中：
$沿着您创建的边缘上的字符以及后缀链接链逐一插入最终标记。更复杂的重复情况Ukkonen 算法（详细信息请参见此处）的关键是 O(n) 是它维护了在何处进行插入的“内存”，其形式为 (a) 指向前一个插入位置的指针，以及 (b) ) 后缀链接网络。该网络可能很大，但每个内部节点只有一个后缀链接，因此其大小仍然是 O(n)。