BF、KMP、BM、Sunday 算法解析
BF、KMP、BM、Sunday算法讲解
字串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一。
事实上也就是从一个母串中查找一模板串，判定是否存在。
现给出四种匹配算法包括BF（即二维循环匹配算法）、KMP、BM、Sunday算法，着重讲KMP算法，其他算法尽量详细讲解，有兴趣的读者可自行查找其它相关资料了解其它算法，当然本文也会推荐一些网址供读者参考。
事实上本博文也是作者阅读了其它博文，然后根据自己的在理解过程中遇到的问题加以阐述，总结而来的，尤其是多次阅读了July的博文。
本文可能会给一部分读者阅读带来不便，所以在本文开始部分就推荐读者相关博文，若读者已经掌握了相关算法，就不要浪费时间继续浏览本博文了，干点其他有意义的事吧：
July博文（强力推荐）http://blog.****.net/v_july_v/article/details/7041827
注：为方面书写，S称作母串，T称作模板串
一、BF：二维循环匹配算法
算法比较简单，不再给予相关解释，直接给出代码，如下：
1 int Search(const string& S, const string& T) { 2 3 int i = 0; 4 int j = 0; 5 6 while(S[i] != ‘\0’ && T[j] != ‘\0’) { 7 if(S[i] == T[j]) { 8 ++ i; 9 ++ j; 10 } else { 11 i = i - j + 1; 12 j = 0; 13 } 14 } 15 16 if(T[j] == ‘\0’) 17 return i - j; 18 19 return -1; 20 }
从代码可以看出，此算法的时间复杂度为O()，相当耗时，一般不采用此算法。但是读者一
定要明确知道此算法的运行过程，KMP算法就是在此基础上改进而来的。
二、KMP算法
此算法是D.E.Knuth与V.R.Pratt 和J.H.Morris同时发现的，取三人名字首字母便得到了KMP，
也称作为克努特-莫里斯-普拉特操作。此算法的时间复杂度为O(n+m)，n为S的长度，m为T的长
度。
假设S为
BBCABCDABABCDABCDABDE
T为
ABCDABD
如果按照二维匹配算法，那么过程如下：
第一步，从S与T首字符开始匹配
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
第二步，匹配到此处（为方便说明，省去了不必要的匹配过程）
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
第三步，根据首字符相匹配可得，可以继续执行T遍历，查找S中的子串
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
到了此处我们发现出现了不匹配现象，如果按照二维循环匹配算法，那么下一步必然会这样：
（1）
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
紧接着又会出现不匹配，直到运行到下面的结果：
（2）
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
让我们算一下，从第三步下标的位置到（2）这一步T的下标共移动了几次呢？？答案是6次
（但愿我没算错）！！如果我们直接从第三步移动到（2）这一步是不是只需要一次就可以了呢
，这样算下去的话,能减少多少不必要的匹配时间！！
因此，KMP算法诞生了，按照以上的步骤（运行到第三步后直接调转到（2）），给出相关代码：
1 int KMP_Search(const string& S, const string& T) { 2 3 int i = 0; 4 int j = -1; 5 int sLen = S.size(); 6 int tLen = T.size(); 7 8 while(i < sLen && j < tLen) { 9 if(j == -1 || S[i] == T[j]) { 10 ++ i; 11 ++ j; 12 } else { 13 j = next[j]; 14 } 15 } 16 17 if(j == tLen) 18 return i - j; 19 20 return -1; 21 }
以上代码可以看出，关键的实现在于next数组，所以读者会问next数组里面保存了什么，能
够实现这么强大的功能？？下面将给予解答……
事实上next[k]数组保存了T前k-1位相等的后缀和前缀的最大长度，next[0]为-1。
以T为”ABCDABD”为例，即：
|
k值 |
前缀 |
后缀 |
最长相等的前缀与后缀 |
next[k] |
|
0 |
空 |
空 |
空 |
-1 |
|
1 |
空 |
空 |
空 |
0 |
|
2 |
A |
B |
空 |
0 |
|
3 |
A、AB |
C、BC |
空 |
0 |
|
4 |
A、AB、ABC |
D、CD、BCD |
空 |
0 |
|
5 |
A、AB、ABC、ABCD |
A、DA、CDA、BCDA |
A |
1 |
|
6 |
A、AB、ABC、ABCD、ABCDA |
B、AB、DAB、CDAB、BCDAB |
AB |
2 |
|
7 |
A、AB、ABC、ABCD、ABCDA、ABCDAB |
D、BD、ABD、DABD、CDABD、BCDABD |
空 |
0 |
接着，读者可能会问为什么要保存它？？
不得不说，上述表格中的数据确实说明不了什么，而且还有可能使读者更加困惑，不过没关
系，请耐心继续往下看，一会就会明白了……
借用第三步得到的状态：
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
S与T分别匹配到A与D处，如果按照二维匹配算法，下一步就会这样：
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
S的’B’与T的’A’匹配辨别，事实上就是（加重部分）的匹配，
B B C A B C D A B A B C D A B C D A B D E
↨
A B C D A B D
不成功匹配字符串”BCDABA”中的”BCDAB”正好是T中匹配成功的部分，也就是T中
”ABCDAB”的字串，也是”ABCDAB”的一个后缀，这个后缀正在与”ABCDAB”进行匹配，
那么所可能匹配成功的最大长度则是”ABCDAB”删去最后一个字符得到字符串”ABCDA”
的长度，这个串也是”ABCDAB”的一个前缀，这也就是相当于”ABCDAB”的前缀和后缀在
匹配，讲到这里，读者应该似乎明白了点什么吧，上述表格似乎有点说法，是吧？？那么，
接着说，既然是一个字符串的前缀和后缀进行匹配，也就是”BCDAB”和”ABCDA”进行匹配，
即：
B C D A B B C D A B B C D A B
↨ ↨ ↨
A B C D A A B C D A A B C D A
B C D A B B C D A B
↨ ↨
A B C D A A B C D A
其实以上五个匹配过程也可以这样看：
B C D A B C D A B D A B
↨ ↨ ↨
A B C D A A B C D A B C
A B B
↨ ↨
A B A
你发现了什么？？
好吧，那我说一下我的发现：前缀”ABCDA”一直在与后缀”BCDAB”匹配，如果匹配不成功
，那么前缀”ABCDA”的前缀就再与后缀”BCDAB”的后缀继续匹配……所能匹配成功的最大长度
就是这一步：
B C D A B
↨
A B C D A
这一步所得到的最大长度就是1，回到next数组，此时的k值恰好为5，next[5]为1，继续匹
配将会得到：
B C D A B
↨
A B C D A
此时，k为6，next[k]为2！！
讲到这里，不知道读者是否明白？？我已经尽力让读者明白了，如果仍不明白，看来我的表
述能力存在缺陷，有待提高……
总结起来，就是上述表格所描述的那样，T的前k-1位的后缀和前缀一直在匹配。
希望读者能够好好理解一下上述过程，如果实在不理解，可以留言抑或参考推荐的博文。
OK，下一步用代码求解next数组。
1 void getNext(const string& T) { 2 3 next[0] = -1; 4 int i = 0; 5 int j = -1; 6 7 while(T[i] != ‘\0’) { 8 if(j == -1 || T[i] == T[j]) { // 这个if应该难不倒读者 9 ++ i; 10 ++ j; 11 next[i] = j; 12 } else { // 关键在这里，如果不相等，那么j就 13 j = next[j]; // 必须回退 14 } 15 } 16 17 }
到了这里，至于代码为什么要这么写需要读者自己独立思考一下了……
至于时间复杂度为什么是O(n+m)就不给予证明了，推荐的July博文有明确证明。
注：n为S长度，m为T长度
下面再给出next数组的优化。
读者可能会问next数组为什么需要优化？？在这里举出一个例子进行说明：
假设母串S为
aaabaaaab
模板串T为
aaaab
当匹配到这里的时候：
a a a b a a a a b
↨
a a a a b
按照上述next数组保存的结果进行匹配，可以发现S[3] != T[3]，那么下一步就需要根据
next[3] = 2进行匹配，然后再根据next[2] = 1进行匹配……直到匹配到T的首字符仍然匹配不
成功为止。那么在求解next数组的时候就可以预判一下，使得在上述匹配不成功的时候直接
滑向首字符，省去不必要的匹配过程。也就是说在S[i] == T[j] 时，当S[i + 1] == T[j + 1] 时，
不需要再和T[j]相比较，而是与T[next[j]]进行比较。那么，next数组求解可以改为下述代码：
1 void getNextval(const string& T) { 2 3 next[0] = -1; 4 int i = 0; 5 int j = -1; 6 7 while(T[i] != ‘\0’) { 8 if(j == -1 || T[i] == T[j]) { 9 ++ i; 10 ++ j; 11 // 修改部分如下 12 if(T[i] != T[j]) 13 next[i] = j; 14 else next[i] = next[j]; 15 } else { 16 j = next[j]; 17 } 18 } 19 20 }
ok，整理一下KMP完整代码：
1 void getNext(const string& T) { 2 next[0] = -1; 3 int i = 0; 4 int j = -1; 5 6 while(T[i] != ‘\0’) { 7 if(j == -1 || T[i] == T[j]) { 8 ++ i; 9 ++ j; 10 next[i] = j; 11 } else { 12 j = next[j]; 13 } 14 } 15 } 16 17 void getNextval(const string& T) { 18 next[0] = -1; 19 int i = 0; 20 int j = -1; 21 22 while(T[i] != ‘\0’) { 23 if(j == -1 || T[i] == T[j]) { 24 ++ i; 25 ++ j; 26 27 if(T[i] != T[j]) 28 next[i] = j; 29 else next[i] = next[j]; 30 } else { 31 j = next[j]; 32 } 33 } 34 } 35 36 int KMP_Search(const string& S, const string& T) { 37 int i = 0; 38 int j = -1; 39 int sLen = S.size(); 40 int tLen = T.size(); 41 42 while(i < sLen && j < tLen) { 43 if(j == -1 || S[i] == T[j]) { 44 ++ i; 45 ++ j; 46 } else { 47 j = next[j]; 48 } 49 } 50 51 if(j == tLen) 52 return i - j; 53 54 return -1; 55 }
ok， kmp算法介绍完毕，下面介绍BM算法~
三、BM算法
事实上KMP算法并不是最快的匹配算法，BM算法(1977年，Robert S.Boyer和J
Strother Moore提出)要比KMP算法快，它的时间复杂度为O(n)（平均性能为O(n)，
但有时也会达到O(n * m)，而且书写代码要复杂，不细心的读者很容易写错），BM算法
采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，
来决定向右跳跃的距离。
例如：
第一步：
A B C D E F G H I
↨
C D E F G F
然后向前匹配：
A B C D E F G H I
↨
C D E F G F
这就是从后往前匹配。
BM算法定义了两种规则：
注：为方面书写，S称作母串，T称作模板串
注：规则读一遍即可，下述图文解释匹配过程可完全解释规则含义。
注：网页上关于BM算法的规则说明原理都是一样的，只不过是表述不同。
A B C D E F G H I
↨
C D E F E F
如上图所示，蓝色字符串“EF”就是好后缀，黄色字符“D”就是坏字符。
1）坏字符规则
在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：
I.如果字符x在T中没有出现，那么从字符x开始的m个文本显然不可能与S在此处的字符
匹配成功，直接全部跳过该区域即可。
II.如果x在T中出现，选择最右该字符进行对齐。
2）好后缀规则
若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：
I.如果在T中其他位置存在与好后缀相同的子串，选择最边右的子串，将S左移使该子
串与好后缀对齐（相当于T右移）。
II.如果在T中任何位置不存在与好后缀相同的字串，查找是T中否存在某一前缀与好后
缀相匹配，如果有选择最长前缀与S对齐，相当于S左移或者T右移；如果不存在，那么直
接跳过该后缀，T的首字符与S好后缀的下一字符对齐。
坏字符规则图文解释：
(1)
A B C D E F G H
↨
H I J K
不匹配，直接跳过，得到：
A B C D E F G H
↨
H I J K
(2)
A B C D E F G
↨
A D D F
字符"D"在T中存在，那么得到：
A B C D E F G
↨
A D D F
好后缀规则图文解释：
(1)
A B C D E F G H I J K
↨
A E F A E F
字符"A"与"D"不匹配，好后缀"EF"在T中存在，那么得到：
A B C D E F G H I J K
↨
A E F A E F
(2)
A B C D E F G H I J K L
↨
F G F A E F G
T中存在前缀“FG”与后缀“FG”相匹配，那么得到：
A B C D E F G H I J K L
↨
F G F A E F G
如果是这样：
A B C D E F G H I J K L M N
↨
F A F A E F G
不存在前缀与任一后缀匹配，那么得到：
A B C D E F G H I J K L M N
↨
F A F A E F G
ok，原理说明完毕，下面就是代码求解：
注：网上诸多作者均给出了详细求解代码，可是求解代码比较晦涩难懂，没有比较好的注释
以帮助读者完全理解，所以在此根据编者自己的理解，给出了晦涩代码段的相关注释。
先给出BM算法的匹配代码：
注：bmG表示好后缀数组，bmB表示坏字符数组
1 int BM(const string& S, const string& T, int bmG[], int bmB[]) { 2 3 int sLen = S.size() - T.size(); 4 int tLen = T.size(); 5 int i = 0; 6 7 get_bmB(T, bmB); 8 get_bmG(T, bmG); 9 10 while(i <= sLen) { 11 int j = tLen - 1; 12 // 出现不匹配字符或者匹配成功循环结束 13 for( ; j > -1 && S[i + j] == T[j]; --j) ; 14 15 // 匹配成功 16 if(j == -1) 17 return i; 18 19 // 选择好后缀与坏字符中移位最大者，tLen - 1 - j表示的是该字符距字符串尾部的距离，bmB[S[i + j]]表示的是该字符 20 // 出现在T中的最右位置距字符串尾部的距离。 21 i += max(bmG[j], bmB[S[i + j]] - (tLen - 1 - j)); 22 } 23 24 return -1; 25 }
那么，下面就需要求解bmG数组和bmB数组了，由于求解bmG
上一篇：
Imagetech bios 设置智能风扇速度 Imagetech 主板调整风扇速度
下一篇：
BM 算法的 C/C++ 代码实现