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 e

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.