8.5 Heuristic for Approximate Pattern Matching with Differences

The heuristic method described in this section finds a prefix of x, a suffix of x, or the entire string x in a text y with k differences. It partially uses dynamic programming techniques.

We refer to the diagonals of the set

by means of an integer d. The diagonal d is the set of pairs ( i, j) for which

The pattern matching method is parameterized by two integers ?, k > 0. It proceeds in three phases. In the first phase, all the positions of factors of length ? of the string that occur in y are found. This phase is realized with the help of a hashing technique. During the second phase, the diagonal d containing the largest number of factors of length ? of the string is selected. The third phase consists in finding an alignment by dynamic programming in a strip of width 2 k around the diagonal d.

We now describe the details of each phase of the computation.

We define the set Z _? by

In other words, the set Z _? contains all the pairs ( i, j) for which the factor of length ? starting at position i on x is identical to the factor of length ? starting at position j on y. With the notation of...