News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.