A COMPARISON OF APPROXIMATE STRING-MATCHING ALGORITHMS

Experimental comparisons of the running time of approximate string mat ching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k, the task is to find a ll approximate occurrences of the pattern in the text with at most k d ifferences (insertions, deletions, changes). We consider seven algorit hms based on different approaches including dynamic programming, Boyer -Moore string matching, suffix automata, and the distribution of chara cters. It turns out that none of the algorithms is the best for all va lues of the problem parameters, and the speed differences between the methods can be considerable.