An Improved Algorithm For Approximate String Matching
Zvi Galil, Kunsoo Park · SIAM Journal on Computing · 1990
Given a text string, a pattern string, and an integer k, a new algorithm for finding all occurrences of the pattern string in the text string with at most k differences is presented. Both its theoretical and practical variants improve upon the known algorithms.