Fast string matching with k differences

摘要

Consider the string matching problem where differences between characters of the pattern and characters of the text are allowed. Each difference is due to either a mismatch between a character of the text and a character of the pattern or a superfluous character in the text or a superfluous character in the pattern. 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 kdifferences. It runs in O(m+nk2) time for an alphabet whose size is fixed. For general input the algorithm requires O(m log m +nk2) time. In both cases the space requirement is O(m).