进击算法：字符串匹配的 BM 算法
进击算法：字符串匹配的 BM 算法
BM 算法介绍
各种文本编辑器的 "查找" 功能（Ctrl+F），大多采用 Boyer-Moore 算法。
Boyer-Moore 算法不仅效率高，而且构思巧妙，容易理解。1977 年，德克萨斯大学的 Robert S. Boyer 教授和 J Strother Moore 教授发明了这种算法。
下面我根据书籍 Algorithms on Strings, Trees, and Sequences 的第2章 Chapter 2 - Exact Matching: Classical Comparison-Based Methods 来介绍 BM 算法。
好后缀
假设匹配过程中发现x[i]=a 和 y[i+j] = b 不同，此时当前匹配的信息有：
x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u x[i] != y[i+j]
此时我们假设能找到u在x中的最右出现位置，则可以直接将x向右滑动shift距离。
but，如果我们没在x中找到u，则我们尝试去找到y[i+j+1 .. j+m-1]的最长后缀v，同时v也是x的前缀。
总结下上面两种情况：
- u可以完整的再次出现在x中
- u的后缀是x的前缀
坏字符
我们找到 y[i+j]=b 在x中最右出现的位置，如果没找到直接左对齐y[i+j+1]：
我们可以发现，坏字符的情况中，有可能shift是负数。
移动
我们可以根据上面的 好后缀和坏字符分别计算出 shift(好后缀) 和 shift(坏字符) ，我们最后真正移动的shift则是 max(shift(好后缀),shift(坏字符))。
算法实现
下面我们来分别计算 shift(好后缀) 和 shift(坏字符)。
先来求shift(坏字符)，具体算法如下：
上面图中第一个说明是尾部不匹配的时候，我们查找字符a在pattern中的位置，假设是i，则Pattern shift的距离是 n-i
第二是是说如果失配发生在pattern中第j个位置，此时字符a在pattern中的位置为i，此时shift为j-i，此时意味着$i<j$，如果$i>=j$的话，此时我们只能取shift=1，下面我们来计算
// 整个下标从1开始
void PreBmBc(char *pattern, int n, int bmBc[])
{
int i;
for(i = 0; i < 256; i++)
{
bmBc[i] = 0;
}
for(i = 1; i <=n ; i++)
{
bmBc[pattern[i]] = i;
}
}下面我们来看好后缀怎么算计：
先看上图，我们定义L(i)为最大的小于n的位置，满足 P[i..n] 是 P[1..L(i)] 的后缀。 接着我们定义 L'(i)，其含义如上图，我们在L(i)的基础上，定义P[i-1] != P[L'(i)-n+i-1]。
举个例子：
接着我们定义$N_j(P),N_j(P)$为P[1..j]和P[1..n]最长公共后缀。
我们来看下定义P[1..j]，假设存在 i 满足L‘(i)=j，即P[i..n]是同后缀，并且P[i-1]!=P[j-n+i-1]也不同，即$N_j(P)=|P[i..n]| = n-i+1$，此时L'(i)=j，于是我们就有了下面的算法:
for i=1 to n, do L'(i) = 0
for j=1 to n-1, do
i = n - Nj(P) + 1
L'(i) = j上面算法中我们是假设已经知道了Nj(P)了，然后通过Nj来计算出L'(i)，那我们怎么计算Nj呢？
// 后缀长度
void SuffixLength(const char *pattern, int n, int N[]) {
for (int j = 1; j < n; j++) {
int i;
for (i = 0; pattern[n - i] == pattern[j - i] && i <= j; i++) {
}
N[j] = i;
}
N[n] = n;
}计算完Nj，下面计算L'：
void CalL(const char* pattern, int n, int L[], const int N[]){
for (int i=1;i<=n;i++){
L[i] = 0; // L[1] 是没意义的，这里也初始化为0
}
for (int j=1;j<n;j++){ // N[n] 是没有意义的，或者说 N[n] 一定为 n
if (N[j]>0){
int i = n - N[j] + 1;
L[i] = j;
}
}
}下面我们看另一种情况，当我们找不到后缀的时候，即L'(i)=0，我们可以退而求其次，求前缀，看下图：
我们定义 l'(i) 是P[i..n]的最长后缀同时也是P[1..n]的前缀，如果不存在这样子的前缀，则l'[i] = 0，此时的含义是说，此时shift=n，为什么移动最大呢？因为我们先去找Patten中是否存在P[i..n]，因为如果要匹配，则pattern中必须要存在P[1..L'(i)]，但是不幸的是没找到，这个时候我们可以直接先shift i-1，然后在慢慢右移，直到 l'(i)，这个过程如下图：
下面就是怎么去计算l'(i)了。
我们如果假设l'(i)存在，即l'(i) = j>0，那么此时Nj(P) = j，并且此时 j 肯定小于等于 |P[i..n]| = n - i + 1，有了这么个洞见以后，我们再来看怎么计算l'(i).
假设N[j] == j, j<=n-i+1 => i<=n-j+1，此时j越大，i越小，因此我们就可以这么做了:
for j=1 to n-1:
if Nj == j:
for i from 1 to n-j+1
l'(i) = j代码如下：
void Call(const char* pattern, int n, int l[], const int N[]){
for (int i=1;i<=n;i++){
l[i] = 0; // l[1]其实没有意义，
}
for(int j=1;j<n;j++){
if (N[j] == j){
for (int i=1;i<=n-j+1;i++){
l[i] = j;
}
}
}
l[1] = 0;
}现在我们来看下怎么根据L'(i)和l'(i)来计算shift的距离：当P[i-1] != T[k] 的时候，如果 L'(i) > 0，则移动 n - L'(i)，否则移动 n - l'(i)，此处需要注意一个特殊情况，即 i=n 的时候，我们需要移动 1 位。
代码如下：
void PreBmGs(const char *pattern, int n, int bmGs[]) {
// const char* p = pattern - 1; // 让下标从1开始
vector N(0,n+1);
vector L(0,n+1);
vector l(0,n+1);
SuffixLength(pattern, n, N.data());
CalL(pattern,n,L.data(),N.data());
Call(pattern,n,l.data(),N.data());
for (int i=1;i<n;i++){
if (L[i]>0){
bmGs[i] = n - L[i];
}else {
bmGs[i] = n - l[i];
}
}
bmGs[n] = 1; // special case
}好了，现在一切就绪，我们开始整个搜索过程了，完整的搜索代码见github地址
另外一个完整搜索过程的图示可以看search examples。
你的鼓励是我继续写下去的动力，期待我们共同进步。
这个时代，每个人都是超级个体！关注我，一起成长！