我正在使用 Ukkonen 的算法来构建后缀树，但我不理解作者对其线性时间复杂度的解释的某些部分。
我已经学习了算法并对其进行了编码，但是我用作主要信息来源的论文（链接如下）在某些部分有点令人困惑，所以我不清楚为什么算法是线性的。
有什么帮助吗？谢谢。
链接到 Ukkonen 的论文：http ://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
问问题
8182 次
1 回答
14
查找 Gusfield 的字符串算法教科书的副本。它有我见过的后缀树结构的最佳阐述。线性是高级算法的许多优化的令人惊讶的结果。
于 2009-08-29T15:18:45.293 回答