Approximate string matching using factor automata

AbstractGiven a text T over alphabet Σ 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 Lk(P) (the set of all strings having at most k differences with respect to pattern P)