The BNDM algorithm uses a table B which, for each character c, stores a bit mask. The mask in Bc is set if and only if xi=c.
The search state is kept in a word d=dm-1 .. d0, where the pattern length m is less than or equal to the machine word size.
The bit di at iteration k is set if an only if x[m-i .. m-1-i+k]=y[j+m-k .. j+m-1]. At iteration 0, d is set to 1m-1. The formula to update d follows d'= (d & B[yj]) << 1.
There is a match if and only if, after iteration m, it holds dm-1=1.
Whenever dm-1=1, the algorithm has matched a prefix of the pattern in the current window position j. The longuest prefix matched gives the shift to the next position.