ukkonen算法编辑距离的解释

Question

我正在寻找一种比正常O（nm）编辑距离算法执行得更好的算法，并且读到它具有O（nd）最坏情况下的时间复杂度，但找不到任何合适的解释为了它。有人可以解释算法的工作原理吗？

Answer 1

对Ukkonen的算法的最好的解释是Ukkonen's suffix tree algorithm in plain English?希望有帮助，它不容易理解。

基本上，Ukkonen的算法允许您快速构建后缀树。然后您必须遍历树来计算编辑距离。