Approximate string matching using factor automata

Given a text T over alphabet Sigma and a complete index for T constructed u sing the finite automaton (called the factor automaton or DAWG) accepting a ll the substrings (factors) of text T. An answer to the query whether a pat tern P occurs in text T with k differences is discussed to be done by an al gorithm having the time complexity independent on the length of text T. The algorithm searches for the final state of the finite automaton accepting t he 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 pat tern P). (C) 2000 Elsevier Science B.V. All rights reserved.