精确字符串匹配（BM算法）
(2007-02-02 16:50)
分类： Algorithms
上一篇文章介绍了精确字符串匹配的 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)，并计算 R(i)。 [查询] k:=n; // n 是 T 中字符的总数 while k<=m do begin i :=n; // i 表示 P 中字符的位置 h :=k; // h 表示 T 中字符的位置 while i>0 and P(i)=T(i) do begin i:=i-1; h:=h-1; end; if i=0 then begin 输出 T 的这个位置上的字符串； k:= k+n-l(2); end else 移动 P(增加 k)，k 取 好后缀规则和坏字符规则决定的最大值 end;
|
预处理阶段可以根据上一篇文章提到的 Zbox 方法进行处理，时间复杂度为线性。
整个算法的时间复杂度最坏的情况是 O(m)，m 是 T 的长度。
