**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:** M^{k}(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: **M^{0} is the M array from above, then M^{h}
can be calculated from M^{h-1} as follows:

Column 0 of M^{h} is all zeroes, and M^{h}(j) = M^{h-1}(j)
OR [Bit-Shift(M^{h}(j-1)) AND U(T(j))] OR Bit-Shift(M^{h-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).