FAST AND PRACTICAL APPROXIMATE STRING-MATCHING

Authors
BAEZAYATES RA PERLEBERG CH
Citation
Ra. Baezayates et Ch. Perleberg, FAST AND PRACTICAL APPROXIMATE STRING-MATCHING, Information processing letters, 59(1), 1996, pp. 21-27
Citations number
33
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
1
Year of publication
1996
Pages
21 - 27
Database
ISI
SICI code
0020-0190(1996)59:1<21:FAPAS>2.0.ZU;2-K
Abstract
We present new algorithms for approximate string matching based in sim ple, but efficient, ideas. First, we present an algorithm for string m atching with mismatches based in arithmetical operations that runs in linear worst case time for most practical cases. This is a new approac h to string searching. Second, we present an algorithm for string matc hing with errors based on partitioning the pattern that requires linea r expected time for typical inputs.