串的匹配模式

BF

暴力匹配，每次右移一位，时间复杂度O(MN)

RK

对BF算法的改进，通过计算哈希值减少比较次数；
基本思想：

• 如果Hash不同，则一定不匹配；
• 如果Hash相同，再逐位比较。

时间复杂度O(MN)，在实际应用中往往较快，期望时间为O(M+N)，如论文查重。

用过哈希表的朋友们都知道，每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是HashCode

HashCode = hash(string)

sssddddeeer --> 39434
sssddddeaar --> 4358

很显然，相对于逐个比较两个字符串，仅比较两个字符串的HashCode要容易的多！

主串：abbcefgh
模式串：bce

第一步，生成模式串的HashCode

哈希算法

哈希算法有很多种，比如：

• 按位相加
  这是最简单的方法，把a视为1，b视为2，c视为3。。。 然后把字符串的所有字符相加，所得结果就是HashCode

  hash(bce) = 2 + 3 + 5 = 10
  

  很容易想到，这个算法可能产生hash冲突，如bce、cbe、bec 的哈希值都是10
• 转为26进制数
  小写字母一共有26个，可以把每个字符当成26进制数来计算，累加所得结果就是字符串的哈希值；

  hash(bce) = 2*(26^2) + 3*(26^1) + 5*(26^0) = 1435
  

  优点是大幅减少哈希冲突，缺点在于计算量较大，可能出现超出整型范围的情况，需要对结果取模。

匹配过程

使用 按位相加 进行匹配，在主串中生成与模式串等长的子串，并计算HashCode

匹配过程.png

第三次子串的哈希值与模式串相同，然后 逐位比较，判定每个字符都是相等的！

增量计算

如果每次都计算子串的哈希值，那么就可能把主串上的所有子串都以计算一遍，总的时间复杂度与BF算法相同--O(mn)！其实，从第二个子串开始，每个子串的哈希值都可以通过计算上一个哈希值的增量得到。

   第一个子串：hash(abb) = 1 + 2 + 2 = 5
   第二个子串：hash(bbc) = hash(abb) - a + c = 5 - 1 + 3 = 7
   ......

增量计算后的时间复杂度是O(n)，相比BF算法，免去了许多无谓的字符比较。
缺点在于，哈希冲突，每次冲突都要逐字比较，如果冲突太多，就会退化成BF算法。

相对而言，BF算法 和 KMP算法 的思路更巧妙，性能也更加稳定。

BM

思想： 有模式串（子串）中不存在的字符，那么肯定不匹配，则向后多移动几位，提高效率；
规则：坏字符规则，好后缀规则 --- 相互独立，相辅相成；

字符串：HERE IS A SIMPLE EXAMPLE
搜索词(模式串)：EXAMPLE

1. 初次比较

首次匹配.png

从右向左开始比较，思路在于 只要尾部字符不匹配，前面的比较也就没有意义
图中，S 与 E 不匹配，S 称之为坏字符，且搜索词中不包含 S，所以移动到坏字符S的下一个；

注：在搜索词中，坏字符对应的角标位置：6

2. 二次比较

二次匹配.png

P 与 E 不匹配，但搜索词中存在 P，则后移两位，让两个 P 对齐。

注：在搜索词中，坏字符对应的角标位置：6；坏字符在搜索词中的角标位置：4。

3. 三次比较

三次匹配.png

坏字符规则：
后移位数 = 坏字符对应搜索词的角标位置 - 搜索词中的坏字符的角标位置
注意：如果搜索词中的坏字符有多个，则取最靠后的那个；如果搜索词中没有坏字符，则返回-1。

由此规则可知：

• 首次比较时的移动位数 = 6 - (-1) = 7
• 二次比较时的移动位数 = 6 - 4 = 2

再来看看本次比较，后四位MPLE 全部匹配，MPLE、PLE、LE、E 都称为好后缀
而 I 与 A 不匹配，所以 I 是坏字符。根据坏字符规则，理应移动 2 - (-1) = 3 位。

好后缀规则：
后移位数 = 好后缀的角标位置 - 好后缀上一次出现的角标位置

举两个栗子

• ABCDAB 的后一个 AB 是好后缀，它的角标位置为 5（从 0 开始，取到最后一个 B），好后缀AB 在搜索词中上一次出现的位置是 1 （第一个 B 的位置），所以后移 5 - 1 = 4 位，前一个AB 移动到后一个AB的位置；
• ABCDEF 的 EF 是好后缀，则 EF 的位角标位置为 5，但前面没有 EF，所以返回 -1，对应的后移 5 - (-1) = 6 位，也就是移动到 F 的下一个位置。

回到三次匹配
所有的好后缀MPLE、PLE、LE、E 中，只有 E 在前面出现过，所以好后缀的后移位置 6 - 0 = 6 位。

坏字符规则移动 3 位，好后缀规则移动 6 位。
Boyer-Moore算法的基本思想：每次后移这两个规则之中的较大值。

三次匹配.png

4. 四次比较

四次匹配.png

按照坏字符规则移动 6 - 4 = 2 位。

5. 五次比较

五次匹配.png

匹配成功！返回角标位置 17

代码实现

BM算法之所以能够在模式匹配中有更高的的效率，主要得益于它构造了两个跳转表：坏后缀表 和 好后缀表。

匹配具有类似特点的模式串和主串时，BM算法非常高效；比如主串aaabaaabaaabaaab，模式串aaaa，每次比对都会后移 4 位。但是，单纯利用坏字符是不够的，因为移动位数可能是负数，比如主串aaaaaaaaaaaaaaaa，模式串baaa，不但不会前进，还可能倒退！所以BM算法还需要好后缀规则。
另外，好后缀规则可以完全独立于坏字符规则来使用，虽然效率可能会降低一些，但在对内存要求苛刻的环境中比较实用。

时间复杂度

BM算法 的时间复杂度非常复杂，最坏时间复杂度O(mn)，最优时间复杂度O(n/m)。
在实际应用中，BM算法 经常能达到平均效率，有些场景下的效率甚至会高于KMP算法。

KMP

KMP算法 与 BM算法十分相似，它们的目标都是让模式串在每一轮多移动几位，减少无谓的字符比较。
为了实现这一点，KMP算法 把专注点放在了 已匹配的前缀，关键在于 next数组 -- 部分匹配表 的推导。