我正在使用Ukkonen的算法来构建后缀树，但是由于线性时间复杂性，我不理解作者解释的某些部分。

我已经学习了算法并对其进行了编码，但是我用作主要信息源（链接的波纹管）的论文在某些地方有些令人困惑，因此对于我而言，我尚不清楚该算法为何是线性的。

有什么帮助吗？谢谢。

链接到Ukkonen的论文：http
:
//www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf