Fast String Matching with Mismatches

We describe and analyze three simple and fast algorithms on the average for solving the problem of string matching with a bounded number of mismatches. These are the naive algorithm, an algorithm based on the Boyer-Moore approach, and ad hoc deterministic finite automata searching. We include simulation results that compare these algorithms to previous works.

Authors

• R.A. Baezayates
• G.H. Gonnet

Keywords

No keywords are indexed for this paper.