Approximate string matching using factor automata

摘要

Given a text T over alphabet Sigma and a complete index for T constructed using the finite automaton (called the factor automaton or DAWG) accepting all the substrings (factors) of text T. An answer to the query whether a pattern P occurs in text T with k differences is discussed to be done by an algorithm having the time complexity independent on the length of text T. The algorithm searches for the final state of the finite automaton accepting the intersection of languages Fac(T) (the set of all factors of T) and L-k(P) (the set of all strings having at most ii differences with respect to pattern P). (C) 2000 Elsevier Science B.V. All rights reserved. [References: 10]