今天上课老师讲了 KMP 的模式匹配算法，看了觉得很不错，不过当 KMP 的 next 数组全为 -1 时，就退化成了朴素的模式匹配，觉得蛮郁闷的，后来自己看了 BM 匹配算法，感觉比 KMP 要好些，嘿嘿……

关于 KMP 算法，好像 Optimistic 写了一篇文章，我在此就不说了，大家有兴趣可以去看看:
    http://www.cppblog.com/sicheng/archive/2006/10/10/13537.html

思想：

假设给定模式串 ”bomb” 和字符串 “universal_super_bomb” ，在进行匹配的时候从最后一个开始比较：

T: universal_super_bomb

P: bomb

很明显， e 在模式串中根本不存在，那么最优的下一步匹配就应该是：

T: universal_ super _bomb

P:       bomb

这样显然效率就要比 KMP 高，而这就是 BM 匹配算法的思想。

方法：

现在那模式串 “bomb” 来举例，模式串长度 m=4 。

BM 模式匹配中有 2 个数组，定一个是 n1 ，一个是 n2 。

n1 的作用是记录字符集中的每个字符在模式中相对于最右端的最近距离， b 离最右端的为 0 ， m 为 1 ， o 为 2 ，其他没有出现的则为 4 ，那么 n1[27]={4,0,4,4,4,4,4,4,4,4,4,4,1,4,2,4,4,4,4,4,4,4,4,4,4,4,4} （ ’_’ 占 n[26] ）。

n2的作用是存储模式中第i个字符不等时，可以移动的位数。
    考虑模式串的子串 s=p_i+1 p_i+1 …p₄ ，相对于模式串本身而言依次向左移动，如果子串 s 没有匹配上，则继续移动子串 s ，直到匹配或者移出模式串最左端，设（匹配或移出） + 之前 子串 s 移动的位数为 n ，则有 n2[i]=m-i+n-1 ，并且令 n2[m-1]=1 。那么对于模式串 ”bomb” 来说 n2[4]={4,4,4,1} 。（ 看这里花了我好久的时间哦，明明是 C++ 数据结构，里面其他地方的下标是从 0 开始，而这里却是从 1 开始，晕死……）

接下来就是如何匹配。匹配的时候先把目标串和模式串左对齐，然后从模式串最右端开始比较， p_i 和 t_j 不相等则计算 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i]) ，并将模式 P 右移 k+i-m 位，用 p_m-1 和 t_j+k 继续比较。

比如：

T: universal_super_bomb

P: bomb

p[3]!=t[3] ，那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ，则将模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=3+4=7 ， p[3] 和 t[7] 进行比较：

T: universal_super_bomb

P:     bomb

p[3]!=t[7] ，那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ，则将模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=7+4=11 ， p[3] 和 t[11] 进行比较：

T: universal_super_bomb

P:           bomb

p[3]!=t[11] ，那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ，则将模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=11+4=15 ， p[3] 和 t[15] 进行比较：

T: universal_super_bomb

P:                 bomb

p[3]!=t[15] ，那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ，则将模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=15+4=11 ， p[3] 和 t[15] 进行比较：

T: universal_super_bomb

P:                        bomb

匹配成功。

（例子有点差哦，没有体现 n1 和 n2 的作用，不好意思啊，各位，原谅我吧…… 偷个懒，懒得换了……）

实现：

再次偷懒，这次不想写，下次写吧，嘿嘿……