这个问题在这里已有答案：
我正在使用Ukkonen的算法来构建后缀树，但是我不理解作者对其线性时间复杂性的解释的某些部分 .
我已经学会了算法并对其进行了编码，但是我用作信息主要信息源的文章（链接波纹管）在某些部分有点令人困惑，因此对我来说，为什么算法是线性的并不是很清楚 .
有帮助吗？谢谢 .
链接到Ukkonen的论文：http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
这个问题在这里已有答案：
我正在使用Ukkonen的算法来构建后缀树，但是我不理解作者对其线性时间复杂性的解释的某些部分 .
我已经学会了算法并对其进行了编码，但是我用作信息主要信息源的文章（链接波纹管）在某些部分有点令人困惑，因此对我来说，为什么算法是线性的并不是很清楚 .
有帮助吗？谢谢 .
链接到Ukkonen的论文：http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
1 回答
找一份Gusfield的string algorithms textbook . 它已经看到了.868495 . 线性度是高级算法的许多优化的令人惊讶的结果 .