ukkonen算法編輯距離的解釋

Question

我正在尋找一種比正常O（nm）編輯距離算法執行得更好的算法，並且讀到它具有O（nd）最壞情況下的時間複雜度，但找不到任何合適的解釋爲了它。有人可以解釋算法的工作原理嗎？

Answer 1

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

基本上，Ukkonen的算法允許您快速構建後綴樹。然後您必須遍歷樹來計算編輯距離。