Vin*_*nto 27 algorithm complexity-theory suffix-tree
我正在使用Ukkonen的算法来构建后缀树,但是我不理解作者对其线性时间复杂性的解释的某些部分.
我已经学会了算法并对其进行了编码,但是我用作信息主要信息源的文章(链接波纹管)在某些部分有点令人困惑,因此对我来说,为什么算法是线性的并不是很清楚.
有帮助吗？谢谢.
链接到Ukkonen的论文:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf