大体思路应该是看懂了，不过具体实现和代码细节还需要时间消化。BM算法的核心思想是通过将模式串沿着主串大踏步的向后滑动，从而大大减少比较次数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时要尽量提高执行效率。这就需要模式串在向后滑动时，遵守坏字符规则与好后缀规则，同时采用一些技巧。

坏字符规则：从后往前逐位比较模式串与主串的字符，当找到不匹配的坏字符时，记录模式串的下标值si，并找到坏字符在模式串中，位于下标si前的最近位置xi（若无则记为-1），si-xi即为向后滑动距离。（PS：我觉得加上xi必须在si前面，也就是比si小的条件，就不用担心计算出的距离为负了）。但是坏字符规则向后滑动的步幅还不够大，于是需要好后缀规则。

好后缀规则：从后往前逐位比较模式串与主串的字符，当出现坏字符时停止。若存在已匹配成功的子串｛u｝，那么在模式串的｛u｝前面找到最近的｛u｝，记作｛u'｝。再将模式串后移，使得模式串的｛u'｝与主串的｛u｝重叠。若不存在｛u'｝，则直接把模式串移到主串的｛u｝后面。为了没有遗漏，需要找到最长的、能够跟模式串的前缀子串匹配的，好后缀的后缀子串（同时也是模式串的后缀子串）。然后把模式串向右移到其左边界，与这个好后缀的后缀子串在主串中的左边界对齐。

何时使用坏字符规则和好后缀规则呢？首先在每次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两者中选择后移距离最大的方案执行。

技巧：
1.通过散列表实现，坏字符在模式串中下标位置的快速查询。
2.每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在模式串中与之匹配的另一个子串的位置。同时预计算模式串中（同长度的）后缀子串与前缀子串是否匹配并记录。在具体操作中直接使用，大大提高效率。
3.如何快速记录模式串后缀子串匹配的另一个子串位置，以及模式串（相同长度）前缀与后缀子串石否匹配呢？先用一个suffix数组，下标值k为后缀子串的长度，从模式串下标为i（0~m-2）的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标值j赋给suffix[k]。若j为0，说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefix[k]设为true，否则设为false。k从0到m（模式串的长度）于是就得到了模式串所有前缀与后缀子串的匹配情况。

曾经一度觉得字符串匹配的几大算法，都是高山仰止的，难以理解。

但是前阵子受两句话启发，从此以后对字符串匹配问题，至少在战略层面藐视了它：
1. 善用之前信息(从信息论的角度：消除信息的不确定性，就是引入信息)

2. 增加效率，在资源有限的情况下，只有想办法少做事情

关于 suffix 和 prefix 的判断取值过程，这样可以帮助理解一下
模式串为：cabcab，所以后缀子串有：
后缀子串 长度
         b 1
       ab 2
     cab 3
   bcab 4
 abcab 5
这些后缀子串都有可能是好后缀{u}！（suffix[k] = j，k{u}是长度，j是在模式串中跟{u}相匹配的{u*}的起始位置）
1. 好后缀是 b => suffix[1] = 2 prefix[1] = false，不是模式串的前缀子串
2. 好后缀是 ab => suffix[2] = 1 prefix[1] = false，不是模式串的前缀子串
3. 好后缀是 cab => suffix[3] = 0 prefix[1] = true，是模式串的前缀子串
4. 好后缀是 bcab => suffix[4] = -1 prefix[1] = false，不是模式串的前缀子串
5. 好后缀是 abcab => suffix[5] = -1 prefix[1] = false，不是模式串的前缀子串
从 1,2,3 中可以看出，如果长度更长的匹配了，前面肯定匹配，因为长度长的包含了长度短的，反之不成立。

这就是结果，然后在看看代码实现：
是从头开始匹配，依次将 b[0, i] 和 b[0,m-1]匹配。
在 while 循环里，依次从后面判断是否匹配，都是先取最后一个来判断，如果匹配就往前，并记录更新位置。如果最后一个都不匹配，那肯定不匹配了

当匹配了 b，就判断 ab是否匹配，接着判断 cab是否匹配... 最后就得到 suffix 和 prefix。