我无法理解构造后缀树的最坏情况时间复杂性是如何线性的 - 特别是当我们需要为可能由重复单个字符组成的字符串构建后缀树时,例如"aaaaa".
即使我要为"aaaaa"构造一个压缩后缀树,我也无法真正压缩任何节点,因为从节点开始的两个边都不能有以相同字符开头的字符串标签.
这将导致高度为5的后缀树,并且在每次插入后缀时,我将需要保持从根到叶的遍历.
这是我接近的方式:后缀:a,aa,aaa,aaaa,aaaaa
创建根节点,创建一个带有'a'的边缘并将其连接到一个新节点,其左边带有"$",并重复此过程直到我们可以aaaaa.
这将导致O(n ^ 2)而不是O(n).我在这里错过了什么？