Re:Damn Cool Algorithms: Levenshtein Automata
by sqrt17 on Thursday July 29, 2010 @03:38AM
(#1556901)
Actually, if you want to see whether the edit distance (Levenshtein) is within a fixed bound, say k, it's no longer O(mn), but around O(kn) (since you're only ever filling a narrow band of width ~k along the diagonal instead of the whole rectangle).
Nonetheless, the DFA construction is priceless if you want flexible matching against a dictionary.
Nonetheless, the DFA construction is priceless if you want flexible matching against a dictionary.