FAST STRING-MATCHING WITH MISMATCHES

Authors
BAEZAYATES RA GONNET GH
Citation
Ra. Baezayates et Gh. Gonnet, FAST STRING-MATCHING WITH MISMATCHES, Information and computation, 108(2), 1994, pp. 187-199
Citations number
15
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
108
Issue
2
Year of publication
1994
Pages
187 - 199
Database
ISI
SICI code
0890-5401(1994)108:2<187:FSWM>2.0.ZU;2-P
Abstract
We describe and analyze three simple and fast algorithms on the averag e for solving the problem of string matching with a bounded number of mismatches. These are the naive algorithm, an algorithm based on the B oyer-Moore approach, and ad hoc deterministic finite automata searchin g. We include simulation results that compare these algorithms to prev ious works. (C) 1994 Academic Press, Inc.