BNDM算法的搜索方法与BDM算法相同，但它使用了位并行来识别子串。

     与原始的BDM相比，BNDM更简单，内存用量更少，具有更好的引用局部性，并且易于扩展到更复杂的模式串的情形。

　  在当前搜索窗口内，设已读入的字符串为u，BNDM算法维护一个集合，记录u在p^rv中的所有出现位置。同shift—and算法一样，该集合可以用一个位向量D来表示。如果子串p_j...p_j+|u|-1等于u，那么D的第m-j+1位是1，表示p的位置j是一个活动状态。

　　当读入一个新的文本字符σ时，要从D更新到D'。D‘的一个活动状态j对应于σu在模式串中的一个起始位置，也就是说：

　　　　* u出现在模式串的位置j+1，即D的第j+1位是活动的；

　　　　*σ在模式串的位置j处出现。

　　同Shift-And算法一样，BNDM算法预先计算一张表B，表B用一个位掩码记录了该字符在p的出现位置。那么利用如下公式，就可以从D更新到D'：

　　　　　　　　　　　　　    D'   <-  (D<<1) & B[σ] ;

　　然而，初始化的时候有些问题需要注意。在初始化D的时候，可能会将D初始化为1^m ,这表示模式串的每个位置都能与空串相匹配。如果这样的话，第一次位移将会得到（D<<1) = 1^m-10,这样会丢失一个子串。最简单的方法是将D的大小设为m+1，并初始化为1^m+1  。然而，这样会将搜索的最大模式串长度限制在w-1以为。为了解决这个问题，可以将以上的公式拆分为两个部分。

　　第一部分进行操作 D₁’ <- D &  B[σ]并且验证可能的匹配；第二部分进行位移 D‘ <- D’₁ <<1。这里使用的初始化是D = 1^m  。如果D’1的位置d_m 是活动的，那么已读入的文本字符串也是p的前缀。

   　BNDM与BDM使用的搜索方法是一样的，区别在于前者用为并行技术进行子串搜索，而后者使用后缀自动机。每当比特位d_m 是活动的时候，窗口中的当前位置就用变量last保存。

      我的BNDM算法c++版实现如下：

 　　

1 void BNDM(char *p,char * t) 2 { 3     int Pstr_len,Tstr_len,i,last,pos,D; 4     int B[128]; 5     Pstr_len = strlen(p); 6     Tstr_len = strlen(t); 7  8     //Preprocessing 9     for(i=0;i<128;i++)10     {11         B[i] = 0;12     }13     for(i=0;i
     
      0)36                 {37                     last = i;38                 }39                 else40                 {41                     cout<<" match at "<
      
       <
       
        << 1;45         }46         pos = pos +last;47     }48 }
       
      
     

　　由实验给出，当字母表小于英文字母表且机器字长大于8位时BNDM算法体现出较高的效率。但并不代表其在处理扩展字符串时的能力。