shr*_*sva 32 algorithm complexity-theory big-o suffix-tree data-structures
要构建一个后缀树,在最坏的情况下,如果字符串的所有字母都不同,那么复杂性将是类似的
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
这是O(n ^ 2).
但是根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要花费O(n)时间.我在这里错过了什么？
tem*_*def 37
你为什么算法应该是Θ(n 2)的直觉是一个好的,但大多数后缀树的设计方式不需要这个时间复杂度.直觉上,你似乎需要Θ(n 2)个不同的节点来保存所有不同的后缀,因为你需要n +(n - 1)+ ... + 1个不同的节点.但是,通常设计后缀树,以便后缀中每个字符不存在单个节点.相反,每个边通常用一系列字符标记,这些字符是原始字符串的子串.你可能看起来需要Θ(n 2)时间来构造这个树,因为你必须将子串复制到这些边缘,但通常这可以通过一个可爱的技巧来避免 - 因为所有边都标有作为输入的子串的字符串,边可以用开始和结束位置标记,这意味着跨越Θ(n)字符的边可以在O(1)时间内构造并使用O(1)空间.
也就是说,构建后缀树仍然很难做到.维基百科中引用的Θ(n)算法并不容易.发现在线性时间内工作的第一个算法之一是Ukkonen的算法,它通常在关于字符串算法的教科书中描述(例如字符串,树和序列上的算法).原始论文在维基百科中链接.更现代的方法通过首先构建后缀数组并使用它来构造后缀树来工作.
希望这可以帮助!