关于字符串匹配算法KMP和BM

Posted on | Edited on | In ,

今天在leetcode终于刷到了string的题，是在一大串字符里面匹配相应的字符。
托python的福，居然被我用暴力破解解决了，虽然结果不是很优雅。

1
2
3
4
5
6
7
8
9
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "": return 0
        
        for i, ch in enumerate(haystack):
            if ch == needle[0]:
                if needle == haystack[i:i+len(needle)]:
                    return i
        return -1

KMP

  • 首先，把这个需要检测的string（a）的第一个和目标string（t）的第一个进行对比，如果不匹配，后移一位
  • 直到找到第一个相同的字母，然后把a和b同时后移一位
    • 还是相同，继续后移
    • 不同（这部分是这个代码的精髓）
      • 一般的思路是把b全都后移一位，但是这样其实消耗挺大的
      • KMP的思路是，既然b的前n位都已经比较过了，那就不要放弃这个信息，不要移动回之前比较过的n位了，继续后移移动到全新的位置
  • 需要移动的位数 = 已经匹配到的字数 - 对应最后一位匹配上的东西的匹配值（由partial match table得出）

如何产生这张表

比如一个单词 bread

  • 前缀：b,br,bre,brea
  • 后缀：read,ead,ad,d
    部分匹配值就是前缀和后缀最长的共有元素长度
  • 比如ABCDABD这个string
    • A前后缀都是空的，长度0
    • AB，前缀A，后缀B，共有长度0
    • ABC，[A, AB]，后缀为[BC, C]，共有元素的长度0
    • ABCD，[A,AB,ABC],[B,BC,BCD] -> 0
    • ABCDA, [A,AB,ABC,ABCD],[BCDA,CDA,DA,A] -> 有一个共有元素A，长度为1
    • ABCDAB,[A, AB, ABC, ABCD, ABCDA],[BCDAB, CDAB, DAB, AB, B] -> 共有元素AB，长度为2
    • “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
      （难点：怎么得到上面的这个长度）

BM

  • 首先将a和b的头对其开始，然后从尾部开始比较。因为如果尾部不匹配的话，这整个一串都不匹配了。知道了这个不匹配的字符之后，这个字符就被称为坏字符
    • 如果这个坏字符包括在单词里面，则需要把这两个对其
    • 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
    • 如果不包含在搜索词里面，那么上一次的位置是-1
  • 最后一位匹配上了，那么就顺着b往前捋
    • 在a里面可以和b后面匹配上的都是good suffix（比如example的e，le，ple等等）
    • 好后缀的后移：后移位数 = 好后缀的位置（最后一个字符为准） - 搜索词中的上一次出现位置
    • 如果没有出现过是 -1
    • 如果有多个好后缀，那么除了最长的好后缀，其他的上一次出现位置必须在头部（b的头部）
  • 在上面两个规则里面，选择移动的最大值
    • 上面两个规则只和搜索词有关，和原来的字符串没关系，所以可以提前生成坏字符和好后缀表，直接比较移动位数