这个问题已经在这里有一个答案：
- Ukkonen的后缀树算法用简单的英语 7回答
我在做与Ukkonen算法构建后缀树了一些工作，但我不理解作者的解释某些部分为它的线性时间复杂度。
我已经学会了算法，并有编码，但我使用的信息（链接波纹管）的主要来源，纸是在一些地方有点混乱，所以它不是真的清楚我为什么算法是线性的。
任何帮助吗？ 谢谢。
链接到Ukkonen的论文： http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
Answer 1:
查找Gusfield的副本字符串算法教材 。 它有后缀树构造我见过的最好展示。 线性是一些高级算法优化的一个令人惊讶的结果。
文章来源: Understanding Ukkonen's algorithm for suffix trees [duplicate]
