首页 > 代码库 > BNDM 算法
BNDM 算法
最近在研究一些字符串匹配算法，也是由于工作上的需要，强力推荐一本书《柔性字符串匹配》，一本很好的书。网上可以随时搜索到。还是说正题吧。
BNDM算法的思想来源于BDM算法思想，类似于shitf-and和kmp之间的区别吧（也不知道是不是准确，有错望大家多指点）。前者都是用位运算模拟后者。好了，那就先介绍一下BDM算法吧！
BDM是基于子串搜索方法，其难点在于怎么搜索子串，书中引入了后缀自动机。对于后缀自动机，我其实没有足够的把握理解它，姑且就当它为一个工具就是了，提供一些状态跳转罢了。现在简单介绍一下它的功能和怎么识别子串。对于这个自动机的实现书上说用一种叫compact suffix tree结构，这些由于时间关系同时这也不是我的重点，故没有去理解。
书中提到后缀自动机的三个性质如下：
第一：字符串u是p（模式串）的一个子串当且仅当p的后缀自动机中存在一条初始状态开始的标号为u的路径。（理解这句话）。
第二：自动机可以识别模式串的所有后缀，从初始状态到某个终止状态的路径上的字符组成的字符串是模式串p的一个后缀。
第三：模式串p=p1p2...pm对应的后缀自动机【用SA（p1p2...pm）表示】可以通过在线的方法在o（0）时间内构建完成，即依次将pj添加到SA（p1p2...pj-1）上，构造SA（p1p2...pj）。
搜索算法：先构建p的反串即pmpm-1...p1的后缀自动机，因为我们是从后向前匹配，搜索模式串的子串。在搜索过程中如果到达了一个终止状态，并且对应的串不是整串p，会得到pmpm-1...p1后缀，即p1p2...pm的前缀，我们将它在窗口中的位置保存在last中，根据性质2，是当前（可不可以更新？不可以！）最长前缀（这是重点）。它是从位置last开始，到窗口末端结束。这种反向搜索有两种结束方式：
第一种：识别子串失败，读入的字符σ，在这后缀自动机的当前状态没有σ的转移。这个窗口向右移动，使它起始位置和last对齐。这样移动窗口不会遗漏任何可能的匹配，（因为我们识别的已经是最长的前缀，不然σ定匹配，因为由于性质2得到的）。
第二种：抵达窗口的起始位置，模式串成功匹配，报告成功，并且像第一种方式移动窗口，使它起始位置和last对齐，因为last最长前缀。
见书本上的图：
理解了BMD算法，现在理解BNDM算法，
BNDM算法和Shift-And算法类似，维护一个集合，这个集合用一个向量D来表示。如果pj...pj+u-1等于u，那么D的第m-j+1位是1，表示p的位置j是一个活动状态。书上的表示这种关系。
表的更新时
当读入新字符σ时，D要更新到D´，D´的一个活动状态j对应于σu在模式串的一个起始位置，也就是说
u出现在模式串的位置j+1，即D的j+1位是活动的，σ在模式串j处出现，从而可以得到表D更新
D´=（D<<1）&B[σ]。
还要注意初始化，因为为了表示空串和模式串的任何位置都匹配，这样D=1m，不然会丢失第一个子串。也可将D大小初始化 为m+1。也可以拆分公式：第一部分D´=D&B[σ],然后在移位D´=D´<<1.其中表B和上面的shift-and类似，可以参考我文章中的shift-and。来理解表B的构建。
见书上伪代码：
自己根据伪代码写的源代码：
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cmath> 5 6 using namespace std; 7 8 void matchString(const string& vSrcStr, const string& vPatternStr, vector<int>& voMatchPosVec) 9 {10 //preprocessing11 int SrcStrLen = vSrcStr.size();12 int PatternStrLen = vPatternStr.size();13 unsigned int BitMask[256] = {0};14 15 for (int i=0; i<PatternStrLen; i++)16 {17 BitMask[vPatternStr[i]] |= 1<<(PatternStrLen-i-1);18 }19 20 //searching21 int Pos = 0;22 while(Pos <= SrcStrLen-PatternStrLen)23 {24 int JPos = PatternStrLen;25 int LastPos = PatternStrLen;26 unsigned int DMask = (unsigned int) pow(2.0,PatternStrLen)-1;27 unsigned int MonitorPos = (unsigned int) pow(2.0,PatternStrLen)-1; //设置防止左移时，高位对判断的影响28 while (DMask&MonitorPos)29 {30 DMask = DMask&BitMask[vSrcStr[Pos+JPos-1]];31 JPos = JPos-1;32 if (DMask&(1<<(PatternStrLen-1)))33 {34 if(JPos>0)35 {36 LastPos = JPos;37 }38 else39 {40 voMatchPosVec.push_back(Pos);41 }42 }43 DMask = DMask<<1;44 }45 Pos = Pos+LastPos;46 }47 }48 49 int main()50 {51 string SrcStr = "aaaaabaaa";52 string PatternStr = "a";53 54 vector<int> MatchPosVec;55 56 matchString(SrcStr, PatternStr, MatchPosVec);57 58 for(vector<int>::iterator Ix=MatchPosVec.begin(); Ix!=MatchPosVec.end(); Ix++)59 {60 cout<<*Ix<<endl;61 }62 63 system("pause");64 return 0;65 }
如果有错误希望大家指出。
BNDM 算法