A fast heuristic for approximate string matching

This work has been supported in part by FONDECYT grants 1950622 and 1960881. Abstract. We study a fast algorithm for on-line approximate string matching. It is based on a non-deterministic nite automaton, which is simulated using bit-parallelism. If the automaton does not t in a computer word, we partition the problem into subproblems. We show experimentally that this algorithm is the fastest for typical text search. We also show which algorithms are the best in other cases, and derive the fastest known heuristic for on-line approximate string matching, when the pattern is not very large. The focus of this work is mainly practical.