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.
void BNDM(char *x, int m, char *y, int n) {
int B[ASIZE];
int i, j, s, d, last;
if (m > WORD_SIZE)
error("BNDM");
/* Pre processing */
memset(B,0,ASIZE*sizeof(int));
s=1;
for (i=m-1; i>=0; i--){
B[x[i]] |= s;
s <<= 1;
}
/* Searching phase */
j=0;
while (j <= n-m){
i=m-1; last=m;
d = ~0;
while (i>=0 && d!=0) {
d &= B[y[j+i]];
i--;
if (d != 0){
if (i >= 0)
last = i+1;
else
OUTPUT(j);
}
d <<= 1;
}
j += last;
}
}
Sorry the new example is not ready... See the Java applet.