I was searching for an algorithm that performs better than normal O(nm) edit distance algorithm, and read that it has O(nd) worst case time complexity but couldn't find any proper explanation for it. Can someone please explain how the algorithm works?
Asked
Active
Viewed 686 times
2
-
Reference links (to the algorithm) would be great in a question like this.. – hyde Oct 12 '14 at 07:45
1 Answers
0
The best explanation of Ukkonen's algorithm is Ukkonen's suffix tree algorithm in plain English? Hope that helps, its not easy one to understand.
Basically Ukkonen's algo allows you to construct a suffix tree quickly. You would then have to traverse the tree to calculate the edit distance.
Community
- 1
- 1
user3240972
- 59
- 6
-
1That link is about suffix trees. The OP's question is about a different algorithm by Ukkonen. – j_random_hacker Oct 12 '14 at 20:05
-
Spot on. saw Ukkonen thought suffix trees :) Much like suffix trees I can't find much on his edit distance algo. – user3240972 Oct 13 '14 at 08:33