我正在使用Ukkonen的算法来构建后缀树，但是由于线性时间复杂性，我不理解作者解释的某些部分。
我已经学习了算法并对其进行了编码，但是我用作主要信息源（链接的波纹管）的论文在某些地方有些令人困惑，因此对于我而言，我尚不清楚该算法为何是线性的。
有什么帮助吗？谢谢。
链接到Ukkonen的论文：http : //www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
查找古斯菲尔德的字符串算法教科书的副本。这是我见过的后缀树构造的最佳说明。线性是高级算法的许多优化的令人惊讶的结果。
