Reduced Nondeterministic Finite Automata for Approximate String Matching.
Jan Holub · Prague Stringology Conference · 1996
We will show how to reduce the number of states of nondeterministic nite automata for approximate string matching with k mismatches and nondeterministic nite automata for approximate string matching with k differences in the case when we do not need to know how many mismatches or di erences are in the found string. Also we will show impact of this reduction on Shift-Or based algorithms.