Richard Cole, Ramesh Hariharan
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,, 1998, 463-472.
We give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. The first algorithm, which is quite simple, runs in time O((nk^3/m)+n+m) on all patterns except mostly periodic strings (defined later). The second algorithm runs in time O((nk^4/m)+n+m) on mostly periodic patterns. The two classes of patterns are easily distinguished in O(m) time.
postscript of full paper