String matching with k differences by finite automata
B. Melichar · 1996
Approximate string matching is a sequential problem and therefore it is possible to solve it using finite automata. A nondeterministic finite automaton is constructed for string matching with k differences. It is shown, how dynamic programming and "shift-and" based algorithms simulate this nondeterministic finite automaton. The corresponding deterministic finite automaton have O((k+2)/sup m-k/*(k+1)!) states, where m is the length of the pattern and k is the number of differences. The time complexity of algorithms based on such deterministic finite automaton is O(n), where n is the length of text.