纸上得来终觉浅，绝知此事要躬行
简介
BM算法的核心思想是通过将模式串沿主串大踏步向后滑动，从而大大减少比较次数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时尽量提高执行效率。这需要模式串在向后滑动式，遵守坏字符与好后缀规则，同时采用一些技巧。
坏字符规则
从后往前逐位比较模式串与主串的字符，当找到不匹配的坏字符时，记录模式串的下标值si，并找到坏字符在模式串中，位于下表si前的最近位置xi(若无则记为-1), si-xi即为向后滑动距离（ps：是否可以加上xi必须在si前面，以防止计算出来负数）。但是坏字符规则向后滑动的步幅还不够大，于是需要好后缀规则。
好后缀规则
从后往前逐位比较模式串与主串的字符，当出现坏字符时停止。若存在已匹配成功的子串{u}，那么在模式串的{u}前面找到最近的{u}，记做{u’}。再将模式串后移，使得模式串的{u’}与主串的{u}重叠。若不存在{u’}，则直接把模式串移到主串{u}后面。为了没有遗漏，需要找到最长的、能够跟模式串的前缀子串匹配的，好后缀的后缀子串（同时也是模式串的后缀子串）。然后把模式串向后移到其边界，与这个好后缀的后缀子串在主串中的左边界对齐。
技巧
何时使用坏字符和好后缀规则呢？首先在每一次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两者中选择后移距离最大的方案执行。具体技巧总结：
- 通过散列表实现，坏字符在模式串中下标位置的快速查询
- 每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在模式串中与之匹配的另一个子串的位置。同时预计算模式串中（同长度）后缀子串与前缀子串是否匹配并记录。在具体操作中使用，大大提高效率。
- 上述2技巧如何实现呢？先用一个suffix数组，下标k为后缀子串的长度，从模式串下标为i(0~m-2)的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标j赋给suffix[k]。若j为0，说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefix[k]设为true，否则为false。 k从0到m(模式串的长度)于是就到了模式串所有前缀与后缀子串的匹配情况。
