【模式匹配】之 —— BM算法
- 坏字符规则The Bad Character Algorithm
- 坏字符规则代码实现
- 好后缀规则The Good Suffix Rule
- 好后缀规则代码实现
- 完整的BM算法
- 测试BM算法的代码
源码下载地址：
http://download.csdn.net/detail/sun2043430/5272376
BM算法由坏字符规则和好后缀规则两部分组成。我们一个一个来看。
坏字符规则（The Bad Character Algorithm）
失配时，目标字符串中对应的字符称为坏字符。例如：
下标数：0123456789
目标串：abcdefghijk
模式串：abcab
开始匹配时，发现在下标3位置处失配，目标串的第3个字符是d，那么d就是一个坏字符，我们需要做的就是查看d在模式串第3位之前有没有出现，如果没有出现那么只要包含了目标串第3位的匹配都是不匹配的。如果有出现，选择最近的那个来和目标串对应上，再进行匹配。
例如上面的例子，d在模式串中没有出现过，所以应该将模式串右移4位，跳过目标串的第3位d所在的位置。
如果是下面的情况：
下标数：0123456789
目标串：adcdefghijk
模式串：adcab
当在第3位失配时，应该将模式串的第1位（d）挪到目标串的第3位来继续进行比较。
下标数：0123456789
目标串：adcdefghijk
模式串：__adcab
坏字符规则代码实现
坏字符是目标串中所有字符的非重复集合，需要使用者自己来指定，一般通用的情况，我们可以建立一个unsingled char ch[256]失配跳转数组，来表示所有的字节，然后将模式串从头到尾扫描一遍，填写对应的失配跳转数组。
代码如下：
void BadChar(const char *pPattern, int nLen, int nBadArray[])
{for (int i = 0; i < 256; i++){nBadArray[i] = -1;}for (int i = 0; i < nLen; i++){nBadArray[(unsigned char)pPattern[i]] = i;}
}该代码首先将坏字符数组全部初始化为-1，意思是当失配时，该坏字符没有出现在模式串中，则应该用模式串的-1位置来对应该坏字符，也就是用模式串的第0位对应目标串中坏字符后面的一位。如果坏字符出现在模式串中，则记录最后一个出现位置（这里一个改进的方法是用链表记录所有的出现位置，在失配时查找失配位置之前的一个对应位置，但这种处理方法会增加代码编写复杂度）
例如对于模式串acab，对应的坏字符数组nBadArray[256]中（下标从0开始），nBadArray[a] = 2；nBadArray[b] = 3；nBadArray[c] = 1；其余位置全部为-1。
当模式串和目标串acbdxxxx匹配时，失配在下标2处，坏字符为b，查nBadArray数组，nBadArray[b] = 3，但是3还在当前失配位置2之后，拿模式串的3位置和目标串的2位置比较，模式串是向左移动，显然方向不对，对于这种情况，我们不按照nBadArray数组中的值来移动，而是简单的将模式串右移一位。
以下是按照坏字符规则来查找模式串的代码：
int BadCharSearch(const char* pDest, int nDLen, const char* pPattern, int nPLen, int *nBadArray)
{int nDstart = nPLen-1;while (nDstart < nDLen){int i = 0;for (; i <= nPLen-1 && pDest[nDstart-i] == pPattern[nPLen-1-i]; i++);if (i > nPLen-1){return nDstart - (nPLen-1);}int nIdx = nBadArray[pDest[nDstart-i]];if (nIdx >= nPLen-1-i)//if nIdx is greater than or equal to mismatch position, just move pattern to right 1 character {nDstart = nDstart + 1;}else{nDstart = nDstart + (nPLen-1-i - nIdx);}}return -1;
}好后缀规则（The Good Suffix Rule）
BM算法的好后缀规则有点类似KMP算法中的最长前缀，所不同的是，BM算法从字符串的最后开始逐位向前匹配，如下面的例子：
情况一：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串：cekgek
当从后往前匹配时，在下标3位置失配，此时已经匹配上的好后缀为ek，所以我们在模式串的前面部分中查找是否有ek出现，如果有，我们将前面出现的ek挪过来，再继续和目标串进行匹配。本例中模式串1,2位置为ek，所以我们挪动模式串到下面位置：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串： cekgek
情况二：
如果匹配上的好后缀部分在前面没有找到，此时我们可以寻找好后缀的后缀中是否有匹配模式串的前缀的情况，如下例：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串：kccgek
好后缀ek虽然在模式串的前面部分中没有找到，但是好后缀的一个后缀（k）正好是模式串的一个前缀，所以我们可以将模式串右移到如下位置：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串： kccgek
情况三：
如果满足以上两种情况的子串（1、完整匹配好后缀；2、前缀中有匹配好后缀的后缀的）都不存在，那么该后缀部分可以直接跳过了，因为所有包含或部分包含该好后缀的匹配都将失配。例如下面的情况：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串：abcgek
好后缀是ek，所有包含或部分包含该好后缀的匹配都将失配。所以直接跳过好后缀部分：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串： abcgek
需要注意的是，好后缀规则和KMP算法中NEXT数组一样，如果好后缀在前面的模式串中找到了，但是好后缀和找到的部分之前的一个字符是相同的，比如下面这样：
下标数：0123456789
目标串：abcdekxxxxxxx
模式串：gekgek
0 3（好后缀之前的一个字符和找到的匹配子串之前的一个字符都是g）
好后缀ek，在前面位置1处找到匹配子串，但好后缀之前的一个字符P[3] = g，和位置0处的g是一样的，这时如果我们简单的将模式串向右挪动到如下位置：下标数：0123456789
目标串：abcdekxxxxxxx
模式串： gekgek
因为之前就是因为P[3] = g产生了不匹配，那么此时P[0]仍然 = g，所以也肯定是不能和目标串匹配的，所以对于情况一，我们在找到匹配好后缀的子串时，还要检查前一个字符是否相同，如果相同，这样的子串是不符合要求的（必然导致匹配失败）。
好后缀规则代码实现
根据以上分析，我们可以写出生成好后缀数组的暴力搜索方法，具体实现可以参看july在http://blog.csdn.net/v_july_v/article/details/6545192一文的代码。
这里我介绍一种来自Algorithms.on.Strings.Trees.and.Sequences].(Dan.Gusfield)一书的线性时间复杂度求好后缀数组的方法。
在【模式匹配】之 —— Z-BOX算法一文中，我介绍了Z-BOX的概念，Zi(P)的定义是在i处有向后的最长为Zi(P)个字符和P的前缀匹配，而N-BOX概念如下：
从i处往前数有最长的Ni(P)个字符，这些字符组成的子串匹配P的后缀。
举例如下：
下标数：012345
模式串：kekkek
计算N-BOX数组的过程和计算Z-BOX的过程一样，只不过两者一个从前往后，一个从后往前，只要掌握了Z-BOX算法，就可以同理写出N-BOX的代码：
void NBox(const char *pPattern, int nLen, int *pNBox)
{pNBox[nLen-1] = 0;int l = nLen-1;int r = nLen-1;for (int i = nLen-2; i >= 0; i--){if (i < l){int n = 0;for ( ; i >= n && pPattern[i-n] == pPattern[nLen-1-n]; n++);if (n > 0){r = i;l = i-n+1;}pNBox[i] = n;}else{if (pNBox[i+nLen-1-r] < i-l+1){pNBox[i] = pNBox[i+nLen-1-r];}else{int n = 1;for (int s = l+nLen-1-i; l >= n && pPattern[l-n] == pPattern[s-n]; n++);pNBox[i] = -(l-n-i);l = l-n+1;r = i;}}}
}用上面的代码计算模式串kekkek的N-BOX值如下，和我们分析的一致。
NBox[0] = 1
NBox[1] = 0
NBox[2] = 3
NBox[3] = 1
NBox[4] = 0
计算出N-BOX数组后，我们怎样将其转化为好后缀数组呢？
根据Ni(P)的定义：在i位置向前的最长的Ni(P)个字符（包括i本身）匹配P的后缀。画图如下：
这样，对于好后缀suffix的一个匹配子串就是从i位置向前数Ni(P)个字符所组成的子串。而且因为Ni(P)是从i开始向前能够匹配后缀的最长长度，所以可以保证这两个子串之前的一个字符是不相同的。
但是，长度为Ni(P)的N-BOX值可能不止一个，如果存在多个，我们应该使用离好后缀最近的的一个子串，也就是在模式串中最靠右的一个。
上面讨论的都是针对情况一的，我们可以先对好后缀数组全部赋值为-1，然后从N-BOX数值的前面往后面遍历一遍，填写对应的好后缀数组。然后我们在来看剩下的好后缀数组中=-1的那些，是否可以用情况二来处理。
对于情况二，找到的是模式串P的前缀，匹配好后缀的后缀，说简单点就是最前面的N个字符匹配最后面的N个字符，我们假设最长的相匹配的前缀、后缀串长度为N（可以在处理情况一的时候顺便得到，具体方法见下面代码），那么对于长度超过N的好后缀，如果它在情况一中没有被填写（也就是不存在完整的匹配），那么根据情况二，好后缀的长度为N的后缀，可以和长度为N的前缀匹配。可以根据这一点来移动模式串。具体代码如下：
bool GoodSuffix(const char *pPattern, int nLen, int nGoodArray[])
{//不直接求好后缀数组，因为直接求的话时间复杂度是O（n的平方）//我们先计算出N-BOX数组int *pNBox = new int[nLen];if (!pNBox){return false;}NBox(pPattern, nLen, pNBox);//根据N-BOX确定好后缀的值，首先全部初始化为-1for (int i = 0; i < nLen; i++){nGoodArray[i] = -1;}//第一种情况：完全匹配L'(i)int nMax = 0;for (int i = 0; i < nLen; i++){nGoodArray[nLen-1-pNBox[i]] = i;if (pNBox[i] == i+1){nMax = i+1;}}nGoodArray[nLen-1] = -1;//第二种情况：部分匹配l'(i) 前缀和后缀的匹配if (nMax != 0){for (int i = 0; i < nLen-1-nMax; i++){if (nGoodArray[i] == -1){nGoodArray[i] = nMax-1;}}}nGoodArray[nLen-1] = nLen-2;if (pNBox){delete pNBox;pNBox = NULL;}return true;
}需要注意的是，好后缀数组中填写的下标值是需要对齐到好后缀数组的最后一个字符的（也就是P[len-1]），这一点在进行好后缀匹配的过程中要小心。下面给出根据好后缀规则进行字符串查找的代码：
int GoodSuffixSearch(const char* pDest, int nDLen, const char* pPattern, int nPLen, int *nGoodArray)
{int nDstart = nPLen-1;while (nDstart < nDLen){int i = 0;for (; i <= nPLen-1 && pDest[nDstart-i] == pPattern[nPLen-1-i]; i++);if (i > nPLen-1){return nDstart - (nPLen-1);}int nIdx = nGoodArray[nPLen-1-i];nDstart = nDstart + (nPLen-1 - nIdx);}return -1;
}完整的BM算法
完整的BM算法就是将坏字符和好后缀一起考虑，哪个移动的距离大就选哪个。
int BMSearch(const char* pDest, int nDLen, const char* ppattern, int nPLen, int *nGoodArray, int *nBadArray)
{if (0 == nPLen){return -1;}int nDstart = nPLen-1;while (nDstart < nDLen){int i = 0;for (; i <= nPLen-1 && pDest[nDstart-i] == ppattern[nPLen-1-i]; i++);if (i > nPLen-1){return nDstart - (nPLen-1);}int nIdxGood = nGoodArray[nPLen-1-i];int nShiftGood = nPLen-1 - nIdxGood;int nIdxBad = nBadArray[pDest[nDstart-i]];int nShiftBad = (nIdxBad >= nPLen-1-i) ? 1 : nPLen-1-i - nIdxBad;nDstart += (nShiftGood > nShiftBad) ? nShiftGood : nShiftBad;}return -1;
}测试BM算法的代码
void TestBMSearch()
{int nFind;int nGoodArray[100] = {0};int nBadArray[256] = {0};// 1 2 3 4//0123456789012345678901234567890123456789012345678901234const char dest[] = "abcxxxbaaaabaaaxbbaaabcdaaxb";const char pattern[][20] = {"a","ab","abc","abcd","x","xx","xxx","ax","axb","xb","b","","aaabaaaab","baaaabaaa",};for (int i = 0; i < sizeof(pattern)/sizeof(pattern[0]); i++){BadChar(pattern[i], strlen(pattern[i]), nBadArray);GoodSuffix(pattern[i], strlen(pattern[i]), nGoodArray);nFind = BMSearch(dest, strlen(dest), pattern[i], strlen(pattern[i]), nGoodArray, nBadArray);if (-1 != nFind){printf("Found \"%s\" at %d \t%s\r\n", pattern[i], nFind, dest+nFind);}else{printf("Found \"%s\" no result.\r\n", pattern[i]);}}
}int _tmain(int argc, _TCHAR* argv[])
{TestBMSearch();return 0;
}输出结果如下：
Found "a" at 0 abcxxxbaaaabaaaxbbaaabcdaaxb
Found "ab" at 0 abcxxxbaaaabaaaxbbaaabcdaaxb
Found "abc" at 0 abcxxxbaaaabaaaxbbaaabcdaaxb
Found "abcd" at 20 abcdaaxb
Found "x" at 3 xxxbaaaabaaaxbbaaabcdaaxb
Found "xx" at 3 xxxbaaaabaaaxbbaaabcdaaxb
Found "xxx" at 3 xxxbaaaabaaaxbbaaabcdaaxb
Found "ax" at 14 axbbaaabcdaaxb
Found "axb" at 14 axbbaaabcdaaxb
Found "xb" at 5 xbaaaabaaaxbbaaabcdaaxb
Found "b" at 1 bcxxxbaaaabaaaxbbaaabcdaaxb
Found "" no result.
Found "aaabaaaab" no result.
Found "baaaabaaa" at 6 baaaabaaaxbbaaabcdaaxb源码下载地址：
http://download.csdn.net/detail/sun2043430/5272376