APPROXIMATE STRING-MATCHING WITH SUFFIX AUTOMATA

The approximate string matching problem is, given a text string, a pattern string, and an integer k, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at most k from the pattern. We give a new O(kn) algorithm for this problem, where n is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.