ISSN:
1432-0541
Keywords:
Approximate string matching
;
Edit distance
;
Dynamic programming
;
Suffix automaton
;
Aho-Corasick automaton
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01769703
Permalink