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 = 10hash冲突，如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
- 初次比较
首次匹配.png
从右向左开始比较，思路在于 只要尾部字符不匹配，前面的比较也就没有意义
图中，S 与 E 不匹配，S 称之为坏字符，且搜索词中不包含 S，所以移动到坏字符S的下一个；
注：在搜索词中，坏字符对应的角标位置：6
- 二次比较
二次匹配.png
P 与 E 不匹配，但搜索词中存在 P，则后移两位，让两个 P 对齐。
注：在搜索词中，坏字符对应的角标位置：6；坏字符在搜索词中的角标位置：4。
- 三次比较
三次匹配.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
- 四次比较
四次匹配.png
按照坏字符规则移动 6 - 4 = 2 位。
- 五次比较
五次匹配.png
匹配成功！返回角标位置 17
代码实现
BM算法之所以能够在模式匹配中有更高的的效率，主要得益于它构造了两个跳转表：坏后缀表 和 好后缀表。
匹配具有类似特点的模式串和主串时，BM算法非常高效；比如主串
aaabaaabaaabaaab，模式串aaaa，每次比对都会后移4位。但是，单纯利用坏字符是不够的，因为移动位数可能是负数，比如主串aaaaaaaaaaaaaaaa，模式串baaa，不但不会前进，还可能倒退！所以BM算法还需要好后缀规则。
另外，好后缀规则可以完全独立于坏字符规则来使用，虽然效率可能会降低一些，但在对内存要求苛刻的环境中比较实用。
时间复杂度
BM算法 的时间复杂度非常复杂，最坏时间复杂度
O(mn)，最优时间复杂度O(n/m)。
在实际应用中，BM算法 经常能达到平均效率，有些场景下的效率甚至会高于KMP算法。
KMP
KMP算法 与 BM算法十分相似，它们的目标都是让模式串在每一轮多移动几位，减少无谓的字符比较。
为了实现这一点，KMP算法 把专注点放在了 已匹配的前缀，关键在于 next数组 -- 部分匹配表 的推导。
网友评论