Faster algorithms for string matching with k mismatches
Amihood Amir, Moshe Lewenstein, Ely Porat · 2000
The string matching with mismatches problem is that of finding the number of mismatches between pattern P of length m and every length m substring of the text T . Currently, the best algorithms for this problem are the following. The Landau-Vishkin 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 O(n p m log m). We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time O(n p k log k). We also show an algorithm that solves the above problem in time O((n + nk 3 m ) log k). 1 Introduction String matching, the problem of finding all occurrences of a given pattern in a given text, is a classical problem in computer science. The problem has pleasing theoretical features and a number of direct applications to "real world" problems. The Boyer-Moore [8] algorit...