Simple and efficient string matching with k mismatches

A new approach to SMk is followed based on the determination of the permutations of P in T, and two algorithms for its solution are proposed, which make use of a suffix tree.

Abstract

Given two strings P and T, m=|P|, n=|T|, m0. We follow a new approach to SMk based on the determination of the permutations of P in T, and propose two algorithms for its solution. The first algorithm is very simple. It runs in time O(n log |AP|+rm), where AP is the alphabet of P, and r<n is the number of occurrences in T of the permutations of P with up to k mismatches. The second algorithm, which makes use of a suffix tree, runs in time O(n log |AP|+dk), where d⩽r is upper bounded by the number of distinct permutations of P in T with up to k mismatches. An extensive set of runs shows that rm<nk and d⪡n, and that the running times are strongly reduced, thus making our algorithms important in practice.