上一篇文章介绍了精确字符串匹配的 Zbox 算法，这是一种线性时间复杂度的算法。在这篇文章里，将简要介绍精确字符串匹配的
Boyer-Moore（BM） 算法，这种算法的时间复杂度低于线性，所以是现在用的最多的一种方法。
所谓精确字符串匹配问题，是在文本 T 中找到所有与查询 P 精确匹配的子串。而 BM 算法可以非常有效地解决这个问题，让时间复杂度降到低于线形的水平。
BM 算法主要用了三种巧妙而有效的方法，即从右到左扫描，坏字符规则和好后缀规则。
从右到左扫描的意思是从最后一个字符开始向前匹配，而不是习惯上的从开头向后匹配。
坏字符规则是，从右到左的扫描过程中，发现 Ti 与 Pj 不同，如果P 中存在一个字符
Pk 与 Ti 相同，且 k<i 那么就将直接将 P 向右移使 Pk 与 Ti 对齐，然后再从右到左进行匹配。如果 P 中不存在任何与 Ti 相同的字符，则直接将 P 的第一个字符与 Ti 的下一个字符对齐，再从右到左进行比较。
如图：
T：
a b c b a d
f t a t e
P：
c b a x a
d
P：
c b a x a d
用 R(x) 表示字符 x 在 P 中出现的最右位置，此例中
R(b)=2。
可以看出使用从右到左扫描和坏字符规则可以跳过
T 中的很多位置不去检查，从而使时间复杂度低于线性。
好后缀规则是，从右到左的扫描过程中，发现 Ti 与 Pj 不同，检查一下相同的部分 t 是否在 P 中的其他位置 t' 出现，a) 如果 t 与 t' 的前一个字母不相同，就将
P 向右移，使 t' 与 T 中的 t 对齐。b) 如果 t' 没有出现，则找到与 t 的后缀相同的 P 的最长前缀 x，向右移动P ，使 x 与 T 中 t 的后缀相对应。
如图a)：
N：
1
N：
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
T： a b
c b a d f t b c f a q v t b c e...
P： c b c a b c
e a b
c
P：
c b c
a b c e a b c f
可见，并不是将 P 向右移让 P5 与 T9 对齐，而是让 P2 与 T9 对齐，因为 P1 与 P8 不相同。用 L(i) 表示 t' 的最大位置，此例中， L(9)= 3。
如图b)：
N：
1
N：
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
8
T： a b
c b a d f t b c f a q v t b c e...
P： b c c a b
c e t b c
P： b c c a b c e t b
c
可见，当 P 向左找不到 “tbc”时，就找到 “tbc”的最长与 P 的前缀匹配的后缀，并将 P 向右移。用 l(i) 表示这个最长后缀的长度，这个例子中 i=8。
整个算法是这样的：
|
[预处理] 输入查询字符串 P， 计算 P 中每个位置的 L(i) 和 l(i)，并计算 [查询] k:=n; // n 是 T 中字符的总数 while k<=m do begin i :=n; // i 表示 P 中字符的位置 h :=k; // h 表示 T 中字符的位置 while i>0 if i=0 then end else end;
|
预处理阶段可以根据上一篇文章提到的 Zbox 方法进行处理，时间复杂度为线性。
整个算法的时间复杂度最坏的情况是 O(m)，m 是 T 的长度。
BM 算法中“好后缀”预处理
其实上次在写 BM 算法的原理时，应该把如何实现“好后缀”的预处理一起写上，只是因为急着出去，没有写清楚，只是一带而过，现在把预处理们仔细写一下，希望和对字符串处理技术感兴趣的朋友们探讨。当然，对于 BM 算法还有许多需要思考的，比如证明它的时间复杂度最坏是 O(m)等等问题，并不是一句话就能说明白的。
在上一篇文章中（精确字符串匹配（BM算法））提到了 L(i)，它是用来存储 t' 最靠右位置 j 的，假设用 t 表示
P[i..n], t' 就是在 P 中重复出现 t 的一段。而 P 也需要向右移，使 L(i) 与 T 中的字符对应。
如图：
_____t' _____t' _____t
|
| | | | |
a a b c d a q f b c d e e b c d
| |
L(i) i
那么如何在 O(n) 时间计算出 L(i) 呢？
在这里需要用到一个值 N(j),N(j)是 Zbox (精确字符串匹配（Zbox算法）)的相反概念，且 N(j)= Z(n-j+1)。
如图：
j
Z(j) a c d b a c
d e f
|___|
Z(j)
j
N(j) a f e m o c e
m o
|___|
N(j)
可见，Z(j) 与 N(j) 一个是和前缀相同的 Zbox 长度，一个是和后缀相同的 Nbox 长度。显然可以根据求 Zbox 的方法求出 Nbox,而求 Zbox 的方法非常简单，而且是 O(n) 的，在Zbox 那篇文章中有详细说明。
求出了所有的 N(j) 之后，就可以利用它求 L(i) 了。
算法描述是：
|
for i:=1 to n do L(i):=0 for j:=1 to n-1 do |