A fast bit-vector algorithm for approximate string matching based on dynamic programming
Abstract
The approximate string matching problem is to find all locations at which a query of length m matches a substring of a text of length n with k -or-fewer differences. Simple and practical bit-vector algorithms have been designed for this problem, most notably the one used in agrep . These algorithms compute a bit representation of the current state-set of the k -difference automaton for the query, and asymptotically run in either O ( nm/w ) or O...
Paper Details
Title
A fast bit-vector algorithm for approximate string matching based on dynamic programming
Published Date
May 1, 1999
Journal
Volume
46
Issue
3
Pages
395 - 415
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
- Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.
Notes
History