KMP算法/BF算法/BM算法/RK算法笔记

KMP算法

转载于

https://baijiahao.baidu.com/s?id=1659735837100760934&wfr=spider&for=pc

1. BF算法

正如同它的全称BruteForce一样，BF算法使用简单粗暴的方式，对主串和模式串进行逐个字符的比较





以此类推，一直到第N轮：
当模式串挪动到某个合适位置，逐个字符比较，发现每一位字符都是匹配时，比较结束：

BF算法的缺点很明显，效率实在太低了，每一轮只能老老实实地把模式串右移一位，实际上做了很多无谓的比较。

2. BM算法

而BM算法解决了这一问题。它借助“坏字符规则”和“好后缀规则”，在每一轮比较时，让模式串尽可能多移动几位，减少无谓的比较。

3. KPM算法

与BM类似，目的也是让模式串在每一轮尽量多移动几位

KMP算法和BF算法的“开局”是一样的，同样是把主串和模式串的首位对齐，从左到右对逐个字符进行比较。第一轮，模式串和主串的第一个等长子串比较，发现前5个字符都是匹配的，第6个字符不匹配，是一个“坏字符”：


在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串。第二轮，我们直接把模式串向后移动两位，让两个“GTG”对齐，继续从刚才主串的坏字符A开始进行比较：

主串的字符A仍然是坏字符，这时候的匹配前缀缩短成了GTG，按照第一轮的思路，我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串：

next 数组
next数组到底是个什么鬼呢？这是一个一维整型数组，数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”。

已知next[i]的值，如何推导出next[i+1]呢？让我们来演示一下上述next数组的填充过程：

如图所示，我们设置两个变量i和j，其中i表示“已匹配前缀的下一个位置”，也就是待填充的数组下标，j表示“最长可匹配前缀子串的下一个位置”，也就是待填充的数组元素值。当已匹配前缀不存在的时候，最长可匹配前缀子串当然也不存在，所以i=0，j=0，此时next[0] = 0。

接下来，我们让已匹配前缀子串的长度加1：

此时的已匹配前缀是G，由于只有一个字符，同样不存在最长可匹配前缀子串，所以i=1，j=0，next[1] = 0。
接下来，我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是GT，我们需要开始做判断了：由于模式串当中 pattern[j] != pattern[i-1]，即G！=T，最长可匹配前缀子串仍然不存在。所以当i=2时，j仍然是0，next[2] = 0。

接下来，我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是GTG，由于模式串当中 pattern[j] = pattern[i-1]，即G=G，最长可匹配前缀子串出现了，是G。所以当i=3时，j=1，next[3] = next[2]+1 = 1。

接下来，我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是GTGT，由于模式串当中 pattern[j] = pattern[i-1]，即T=T，最长可匹配前缀子串又增加了一位，是GT。所以当i=4时，j=2，next[4] = next[3]+1 = 2。

接下来，我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是GTGTG，由于模式串当中 pattern[j] = pattern[i-1]，即G=G，最长可匹配前缀子串又增加了一位，是GTG。所以当i=5时，j=3，next[5] = next[4]+1 = 3。

接下来，我们让已匹配前缀子串的长度继续加1：

此时的已匹配前缀是GTGTGC，这时候需要注意了，模式串当中 pattern[j] ！= pattern[i-1]，即T != C，这时候该怎么办呢？
这时候，我们已经无法从next[5]的值来推导出next[6]，而字符C的前面又有两段重复的子串“GTG”。那么，我们能不能把问题转化一下？
或许听起来有些绕：我们可以把计算“GTGTGC”最长可匹配前缀子串的问题，转化成计算“GTGC”最长可匹配前缀子串的问题。

这样的问题转化，也就相当于把变量j回溯到了next[j]，也就是j=1的局面（i值不变）：

回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即T！=C。
那么我们可以把问题继续进行转化：

问题再次的转化，相当于再一次把变量j回溯到了next[j]，也就是j=0的局面：

回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即G！=C。j已经不能再次回溯了，所以我们得出结论：i=6时，j=0，next[6] = 0。
以上就是next数组元素的推导过程。

1. 对模式串预处理，生成next数组
2. 进入主循环，遍历主串
3. 比较主串和模式串的字符
4. 如果发现坏字符，查询next数组，得到匹配前缀所对应的最长可匹配前缀子串，移动模式串到对应位置
5. 如果当前字符匹配，继续循环

4.RK算法

RK算法转载网址https://www.cnblogs.com/hhhuang/p/12325374.html

RK算法全称为Rabin-Karp算法，即由Rabin和Karp两个人发明的。RK算法可以理解为BF算法的升级版。
在BF算法中，每次需要暴力的对比n-m+1个子串和模式串，每次最多需要对比m个字符，实际复杂度比较高。我们对其稍微进行改进，引入哈希算法，来降低时间复杂度。
RK算法思想：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。
因为哈希值是一个数字，数字之间比较是否相等是非常快速的。不过在此之前我们还要遍历子串中的每个字符，来计算子串的哈希值。模式串和子串的比较效率提高了，但是算法整体效率没有提高。所以还要想办法提高计算子串哈希值的效率。
我们假设要匹配的字符集中只包含K个字符，然后用一个K进制数来表示一个子串，这个K进制数转化为十进制数，作为子串的哈希值。可以看下图中的例子：
“657”看作十进制表示，“cba"看作26禁止表示，即只算小写字母有26个字符。

下面以字符串中只包含a-z这26个小写字符为例，在哈希值的计算中有一个特点，相邻两个子串s[i-1]和s[i] (i表示子串在主串中的起始位置，子串长度均为m)，对应的哈希值计算公式有交集。由公式表示如下图：

此外，在计算时为了提高效率，可以使用将26^(m-1)这部分计算先计算好存起来，后面使用时直接查表获取。
RK算法的时间复杂度：
RK算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值的比较。第一部分，可以设计特殊的哈希算法，只需要扫描一次主串便可以求出所有子串的哈希值。时间复杂度为O(n)；第二部分哈希值直接的比较时间复杂度为O(1)，总共需要比较n-m+1个子串，所以时间复杂度也为O(n)。所以整体的时间复杂度为O(n)。
其他可能遇到的问题：
如果模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算的哈希值就会特别大，如果超过了计算机中的整形数据可以表示范围，如何解决？
刚才设计的哈希算法是没有散列冲突的，一个字符串与一个数值对应。但是为了能够将哈希值落在整型数据范围内，可以允许哈希冲突。我们可以更改哈希算法，a-z这26个字母每个对应一个数字，然后将字符串变成将每个字符对应的数字相加，最后的和作为哈希值，这个值就会相对小很多。或者将每一个字母从小到达对应一个素数，这样的冲突概率会降低一些。
现在新的问题时，如何解决冲突，方法很简单，当我们发现一个子串的哈希值跟模式串的哈希值相等时，在对比一下子串和模式串本身就好了。这里也要控制哈希算法冲突概率相对低一些，如果存在大量冲突，RK算法的时间复杂度也会退化，效率降低，极端情况下将会退化为O(n*m)。
思考：在RK算法指向时，可以边计算主串中的子串，边与模式串进行对比，如果哈希值相同，即匹配成功了，那么主串后面的子串就可以不用计算了，直接退出。