Faster algorithms for string matching with k mismatches |
| |
Authors: | Amihood Amir Moshe Lewenstein Ely Porat |
| |
Affiliation: | a Department of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel;b College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280, USA |
| |
Abstract: | The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length m and every length m substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil–Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O(nk). The Abrahamson algorithm finds the number of mismatches at every location in time . We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time . We also show an algorithm that solves the above problem in time O((n+(nk3)/m)logk). |
| |
Keywords: | Design and analysis of algorithms Combinatorial algorithms on words Approximate string matching Hamming distance |
本文献已被 ScienceDirect 等数据库收录! |