The problem of string matching with k differences can be solved by simple modification of the Wagner-Fischer algorithm. This is accomplished by having the entries in the edit distance table represent...

The problem of string matching with k differences can be solved by simple modification of the Wagner-Fischer algorithm. This is accomplished by having the entries in the edit distance table represent the minimum distance between prefix Q(0 . . . i) and any suffix of R(0 . . . j) (Sellers, 1980). This is done by defining the entries in the matrix with the same recurrence relation as D(i,j) = min(D(i – 1,j) + 1, D(i,j – 1) + 1, D(i – 1,j – 1) + c(i,j)), the same boundary condition for column 0: D(i,0) = i, but a different condition for row 0: D(0,j) = 0 to indicate that an occurrence can start at any position of R. In the resulting edit table, any number in the last row that is not greater than k indicates a position in R of the end of a substring of R that has at most k differences with Q. Build such an edit table for strings Q = abcabb and R = acbdcbbcdd.