Name
Abstract | ||
|---|---|---|
The approximate string matching problem is to find all locations at which a query p of length m matches a substring of a text t of length n with at most k differences (insertions, deletions, substitutions). The fastest solutions in practice for this problem are the bit-parallel NFA simulation algorithms of Wu & Manber [4] and Baeza-Yates & Navarro [1], and the bit-parallel dynamic programming algorithm of Myers [3]. In this paper we present modified versions of these algorithms to deal with the restricted case where only insertions and deletions (called indel for short) are permitted. We also show test results with the algorithms. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/978-3-540-30577-4_44 | SOFSEM |
Keywords | Field | DocType |
restricted case,query p,test result,bit-parallel dynamic programming algorithm,bit-parallel nfa simulation algorithm,bit-vector algorithm,fastest solution,length n,k difference,indel distance,approximate string,length m,dynamic programming algorithm,approximate string matching | String searching algorithm,Dynamic programming,Discrete mathematics,Combinatorics,Substring,Commentz-Walter algorithm,Computer science,Algorithm,Approximate string matching,Bitap algorithm,Bit array,Indel | Conference |
Volume | ISSN | ISBN |
3381 | 0302-9743 | 3-540-24302-X |
Citations | PageRank | References |
3 | 0.43 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heikki Hyyrö | 1 | 143 | 15.04 |
| Yoan J. Pinzon | 2 | 158 | 16.81 |
| Ayumi Shinohara | 3 | 936 | 88.28 |