BM算法（手算版）

BM 算法

        BM 算法是一种字符串匹配的算法。
        与 KMP 相比，BM 算法不扫描全部输入字符，平均匹配时间 c・n, 常量 c <1 (随机或真实文本), 但最坏情况是 O (n・m).
        可以将 BM 算法的最坏情况改进到 O (n)：通过记录文本后缀中最长的模式后缀。

要使用 BM 算法，需要知道两个信息：
1. 用于坏字符规则的 bc 数组
2. 用于好后缀规则的 gs 数组

坏字符规则

坏字符规则分为两种情况：
1. 失配位置指向的文本串中对应的字符，不存在于模式串中。

如上图所示，在这种情况下，直接将整个模式串移动到失配位置之后。

2. 失配位置指向的文本串中对应的字符，存在于模式串中，且在失配位置的左边。

坏字符

如上图所示，在这种情况下，将模式串中的文本串中对应的字符放在失配位置上。

需要注意两个问题：
1. 这个 “模式串中的文本串中对应的字符 ”，是整个模式串从右往左数的第一个符合的字符。否则会造成过度左移。
2. 模式串中最后一个字符，不能和任何的失配位置匹配。这是因为 “失配” 的前提是有匹配，而右边第一个字符必然被匹配；否则在右边第一个字符失配，那说明所需要的字符不是这个右边的第一个字符。故最后一个字符对应的位置是从右边数第二个符合数的位置。
如字符串 “GCAGAGAG” 的坏字符表为 (从 0 开始计数，从右往左数)：

char	A	C	G	T
bc[char]	1	6	2	8

        坏字符表不是一直有效的。如果坏字符表中记载的位置，在失配位置的右边，那么可能会造成负位移或原地不动。
        一个解决方法是，记载每次失配位置的左边的第一个符合的字符：但这很麻烦。
        这并不是说位移就是上表的值。位移 = bc [char]- 失配位置 Z。(从右往左数，0 开始)

好后缀规则

好后缀规则分为 3 种情况：

rule3：

如图 14.1，目前匹配好的后缀 u，在模式串中存在。如果有多个，则取最靠右的且 c！=a 的那个，并将其对齐。

rule2：

如图 14.2，目前匹配的好后缀 u，在模式串中其他位置不存在。但它的后缀，和模式串的前缀相同。如果有多个满足的后缀，则取最长的那个后缀，并将其对齐。

rule1：

如图 14.？，目前匹配的好后缀 u，在模式串中其他位置不存在。且它的每一个后缀，和模式串的前缀都不相同。这种情况下，直接将整个模式串移动到当前的最右端之后。

好后缀规则和坏字符规则是可以同时使用的，我们每次取俩者中最大的那个。

如坏字符规则一样，好后缀也有自己的表，叫做 gs 数组。要想得到 gs 数组，首先要利用 suff 数组。

suff 数组：存储从字符 s [i] 向左开始计数的，和模式串最右边字符开始的匹配的字符个数。

如字符串 “GCAGAGAG” 的 suff 为 (从 0 开始计数)：

G	C	A	G	A	G	A	G
1	0	0	2	0	4	0	8

从右往左看：
从 G 开始，GAGAGACG 与 GAGAAGACG 匹配，个数是 8，故填 8。
从 A 开始，没有字符匹配 (因为右边第一个字符是 G)，故填 0。
从 G 开始，GAGA (下一个是 C) 与 GAGA (下一个是 G) 匹配，个数是 4，故填 4。
从 A 开始，没有字符匹配 (因为右边第一个字符是 G)，故填 0。
从 G 开始，GA (下一个是 C) 与 GA (下一个是 G) 匹配，个数是 2，故填 2。
从 A 开始，没有字符匹配 (因为右边第一个字符是 G)，故填 0。
从 C 开始，没有字符匹配 (因为右边第一个字符是 G)，故填 0。
从 G 开始，G (下一个是末尾) 与 G (下一个是 A) 匹配，个数是 1，故填 1。

接下来，我们依次处理 rule1，rule2，rule3，来获得 gs 数组。
为什么是这个顺序：因为 rule1 位移 > rule2 位移 > rule3 位移，大的值被小的值取代，才不会造成过度右移。
具体的理解，可以见高效字符串匹配算法

施加 rule1：
所有的项均有最大位移 8 (字符串长)：

G	C	A	G	A	G	A	G
8	8	8	8	8	8	8	8

施加 rule2：
step1：从右往左扫描模式串，找到第一个下标 (下标从左往右数，从 0 开始计。略过最右边的数)+1=suff [i] 的位置。对上面的例子来说，这个位置是 “i=0”，对应的是最左边的字符 G。
step2：从左往右扫描字符串，将扫描过的位置对应的 gs 数组改为 “当前值 - suff [i]”，直到剩下 suff [i] 个字符。
step3：step 继续向左，step2 继续向右，直到扫描完成。