Improved string matching with k mismatches

Abstract

Given a text string t0 t1 . . . tn_1 , a pattern string p0 p1 .pm-1 and an integer k, k m 5 n, we are interested i n finding all occurrences of the pattern in the text with at most k mismatches, i .e. with at most k location s in which the pattern and the text have different symbols .