BM算法 §

BM（Boyer-Moore）算法是一种高效的字符串匹配算法，在暴力滑动匹配的基础上进行了改良，其核心思想包括坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

坏字符规则 §

假设主串为abcacabdc，模式串为abd

BM算法在进行匹配时，是从模式串的最后一个字符一一向前匹配的。在上例中，先将主串前三位abc与模式串abd进行匹配，先匹配最后一个字符c与d，发现匹配不上，这时去模式串中查找c字符，没有找到，这时就把c叫做一个坏字符。再进行下一轮匹配的时候，直接将模式串右滑3位，用主串的aca与模式串abd进行匹配。同样的，最后一个字符不匹配，a是坏字符，但这一次模式串里面有a字符，因此在滑动时，只向右滑动2个位置。

如果一直去模式串里查找字符，算法效率会变得很低。可以先维护一个哈希表，记录各个字符在模式串中最后一次出现的位置，这样就可以使用O(1)的时间复杂度查找字符。

好后缀规则 §

好后缀规则与坏字符规则类似，假设主串为acabcbcbacabc，模式串为cbbcabc。

首先比较主串的acabcbc与模式串cbbcabc，发现最后两位相同，都是bc。这时bc就是一个好后缀，将模式串中查找好后缀bc，发现模式串的第3位与第4位恰好为bc，在下次滑动的时候，就将主串的bc与模式串中的第3位与第4位对齐，进行下一次匹配。

如果没有在模式串中匹配到好后缀，那么滑动步数的计算会复杂一些，要考虑好后缀的子串是否与与模式串的前缀相同。像在上例中，好后缀bc的子串c，与模式串开头的字母相同，那么在滑动的时候，就需要将两个c对齐，而不是直接滑动到好后缀的后面。