BM算法和KMP算法

BM算法

BM算法可以实现编辑器查找功能。

BM算法匹配规则分为: 坏字符和好后缀原则。
假如在 HERE IS A SIMPLE EXAMPLE 中查找EXAMPLE

坏字符原则

1. 从后往前匹配, 主串中的S和模式串中的E不匹配，S称为坏字符
2. 匹配到了坏字符，在模式串中标记坏字符出现的位置，也就是E所在的位置6(从0开始)
3. 在模式串中搜索坏字符S是否出现在前面。如果有，则标记最靠右的坏字符位置，如果没有，标记坏字符位置为-1
4. 如上面例子，S并没有出现在模式串中，此时后移公式: 移动位置 = 坏字符出现位置 – 模式串中坏字符再次出现的位置，上面的例子就是 移动位置 = 6 – (-1),也就是移动7位。 因为坏字符出现的位置是模式串的第6位(最后一个没匹配上，标记模式串中此处为坏字符位置), S也没有再出现，所以坏字符再次出现的位置是-1
5. 坏字符规律: 如果遇到坏字符，计算移动位置，需要2个位置，第一个是坏字符出现的位置，第二个是坏字符再次出现最靠右的位置，没有再次出现就是-1

好后缀原则

1. 此时匹配到相同的是 MPLE，MPLE称为好后缀
2. 此时的好后缀有MPLE, PLE, LE ,E。4个好后缀.
3. 先判断前面是否还有最长好后缀，也就是MPLE，显然EXA没有。如果有，移动位置 = 最长好后缀的最后一个位置的索引 减去 前面匹配上的子串的最后一个位置的索引。 说的太繁琐，看示例
4. 例如 ABDAB ，假设好后缀是AB，前面ABD里面有好后缀AB，取好后缀的最后一个字符的位置，就是好后缀中的B的位置，也就是4，再取前面出现好后缀的最后一个位置，例如ABD中的B，也就是1.移动位置 = 4 – 1，移动3位。
5. 再判断模式串头部的最长好后缀是什么，例如上面的EXAMPLE，对比上面的好后缀，EXA里没有MPLE，那就看看头部是什么，EXA头部是E，那么移动位置 = 最长好后缀的最后一位索引 – 前面匹配的最长好后缀
6. 移动位置 = 6 – 0等于6
7. 如果前面没有好后缀，那么标记前面出现好后缀的最后一个位置为-1，其实就是直接移动模式串到好后缀的下一位

移动位置取 坏字符和好后缀原则的最大值

KMP算法

1. 从头开始匹配，如上图，B跟A不匹配，后移一位，直到能匹配的上

2. 这里最后一位,空格跟D不匹配，但是前面都匹配上了，要利用匹配上的ABCDAB。
3. 建立一张部分匹配表

搜索词就是前面已经匹配上的字符。
部分匹配值就是前缀和后缀相同元素的长度

计算方式：从A -> AB -> ABC 直到 ABCDABD

• [A]的前缀和后缀都为空，部分匹配值为0
• [AB]前缀为A，后缀为B，没有匹配的，部分匹配值为0
• [ABC]前缀为A、AB，后缀为B、BC，没有匹配的，部分匹配值为0
• ….
• [ABCDA]前缀为A、AB、ABC、ABCD,后缀为A、DA、CDA、BCDA，前缀和后缀中的A是相等的，它的长度为1，所以部分匹配值为1
• [ABCDAB] …. 部分匹配值为2

此时的移动位置 = 已匹配字符串的长度 – 最后的部分匹配值
移动位置 = 6 – 2 = 4

移动了4步之后，AB成功匹配，但是C和空格不匹配。
移动位置 = 2（已匹配长度） – 0（最后部分匹配值） = 2
就这样直到找到了为止。

参考资料
阮一峰大佬的KMP算法
阮一峰大佬的BM算法