了解Ukkonen的算法后缀树 [英] Understanding Ukkonen's algorithm for suffix trees

问题描述

我在做与Ukkonen的算法，一些工作为构建后缀树，但我不理解作者的解释，一些地方为它的线性时间的复杂度。

I'm doing some work with Ukkonen's algorithm for building suffix trees, but I'm not understanding some parts of the author's explanation for it's linear-time complexity.

我已经学会了算法，并有codeD，但我正在使用的信息（链接波纹管）的主要来源纸张有点混乱，在一些地方，所以它不是为我，为什么算法真正明确是线性的。

I have learned the algorithm and have coded it, but the paper which I'm using as the main source of information (linked bellow) is kinda confusing at some parts so it's not really clear for me why the algorithm is linear.

任何帮助吗？谢谢你。

链接到Ukkonen的文章：<一个href="http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf">http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Link to Ukkonen's paper: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

推荐答案

查找Gusfield的<副本的href="http://books.google.com/books?id=STGlsyqtjYMC&lpg=PP1&ots=kiQ7zxM%5Fr8&dq=gusfield%20algorithms%20strings&pg=PP1#v=onepage&q=&f=false">string算法教材。它有后缀树建设我见过的最好展示。线性是一个数字的高级算法的优化的一个令人惊讶的结果。

Find a copy of Gusfield's string algorithms textbook. It's got the best exposition of the suffix tree construction I've seen. The linearity is a surprising consequence of a number of optimizations of the high-level algorithm.

这篇关于了解Ukkonen的算法后缀树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！