## The Shift-And Method

Definition: M(i, j) is an n by (m+1) array with M(i, j) = 1 if P[1..i] = T[j-i+1 .. j] and zero otherwise. In particular, M(i, 0) = 0

Definition: U(x) is a bit-vector of length n that is 1 for each position in P where x occurs

Definition: Bit-Shift(j-1) is the bit-vector obtained by shifting column j-1 of M down one position, dropping the bottom bit and filling in a 1 at the top position.

Algorithm: Column 0 of M is all zeroes, then if M(j) is column j, M(j) = Bit-Shift(j-1) AND U(T(j))

Definition: Mk(i, j) = 1 if P[1..i] and T[j-i+1 .. j] have at most k mismatches, and zero otherwise. Here only mismatches are allowed, though the definition could be extended to handle insertions and deletions.

Algorithm: M0 is the M array from above, then Mh can be calculated from Mh-1 as follows:
Column 0 of Mh is all zeroes, and Mh(j) = Mh-1(j) OR [Bit-Shift(Mh(j-1)) AND U(T(j))] OR Bit-Shift(Mh-1(j-1))
Note that there seems to be a misprint in the book - the last Bit-Shift is missing.

Definition: (Match-counts) MC(i, j) = number of characters that match between P[1..i] and T[j-i+1 .. j]

To calculate the entire array takes time proportional to n*m, but using FFTs, the last row can be calculated in O(m lg m).