Efficient string matching with k mismatches

Given a text of length n, a pattern of length m, and an integer k, we present an algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches. The algorithm runs in O(k(m log m + n)) time.

Authors

• Gad M. Landau
• Uzi Vishkin

Keywords

No keywords are indexed for this paper.