字符串匹配

• BF算法

• RK算法

• BM算法

• KMP算法

相关概念

如果说，在字符串A中查找字符串B，那字符串B就是模式串，字符串A就是主串。主串长度记为n，模式串长度记为m。

BF算法

BF是Brute Force的缩写，BF算法叫作暴力匹配算法，也叫朴素匹配算法。

算法思想：

​ 在主串中检查起始位置分别是0,1,2...n-m且长度为 m的n-m+1个子串，看有没有跟模式串匹配的。

时间复杂度：

​ 理论上，时间复杂度为O(n+m)。

优势：

1. 实际开发中，主串和模式串的长度都不会太长。并且大部分情况下，算法执行效率都会高于O(n+m)。

2. 算法思想简单，代码实现简单，易于调试且不易出错。

RK算法

RK算法全称叫作Rabin-Karp算法。

算法思想：

​ 通过哈希算法对主串中的n-m+1个子串求哈希值，然后逐个与模式串的哈希值比较大小。

​ 如果相等，且确定无哈希冲突产生，则子串和模式串直接匹配；如果相等，且有概率出现哈希冲突，则再比较子串和模式串的具体内容。

哈希算法设计：

​ 如果要匹配字符串的字符集中，只包含K个字符，就可以用一个K进制数来表示一个子串，然后将K进制数转化为十进制数，作为哈希值。

​ 子串哈希值的计算具有规律，可以根据前一个子串的求得后一个子串。

时间复杂度：

​ 时间复杂度为O(n)，但是如果存在大量哈希冲突，时间复杂度就会退化为O(n*m)。

BM算法

• 算法思想：

  在模式串与主串匹配的过程中，当模式串与主串某个字符不匹配，跳过一些肯定不会匹配的情况，将模式串外后多移几位。

  算法需要用到坏字符规则和好后缀规则。

• 坏字符规则：

  从模式串的末尾往前倒着匹配，当出现某个字符无法匹配时，这个字符就叫作坏字符（主串中的字符）。

  当发生不匹配时，把坏字符对应的模式串中的字符下标记作si。

  如果坏字符在模式串中存在，把坏字符在模式串中的下标记作xi。

  如果坏字符在模式串多处出现，此时选择最靠后的那个，避免模式串滑动过多。

  如果不存在，把xi记作-1。

  模式串往后移动si-xi。

• 好后缀规则：

  已经匹配的字符叫作好后缀。

  好后缀记作{u}，拿它在模式串中查找，如果找到了另一个匹配的子串{u*}，就将模式串滑动到子串{u*}与主串{u}对齐的位置。

  如果找不到匹配的子串，则从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的。

• 坏字符代码实现：

  将模式串字符及其下标，都存到散列表。

• 好后缀代码实现：

  好后缀也是模式串本身的后缀子串，所以可以在模式串和主串正式匹配之前，预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。

  使用suffix数组，数组下标k表示后缀子串的长度，下标对应数值存储的是，模式串中跟好后缀相匹配子串的起始下标值。

  使用prefix数组，记录模式串的后缀子串是否能匹配模式串的前缀子串。

  拿下标从0到i(0<=i<=m-2)的子串与整个模式串，求公共后缀子串。如果公共后缀子串的长度为k，就记录suffix[k]=j(j表示公共后缀子串的起始下标)。

  如果j等于0，则公共后缀子串也是模式串的前缀子串，就记录prefix[k]=true。

• 性能分析：

  好后缀规则可以独立于坏字符规则使用。坏字符规则的实现比较消耗内存，为了节省内存，可以只用好后缀规则来实现BM算法。

KMP算法

• 坏字符：

  不能匹配的字符叫作坏字符。

• 好前缀：

  已经匹配的字符串叫作好前缀。

• 最长可匹配后缀子串、最长可匹配前缀子串：

  好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

• 算法思想：

  模式串和主串匹配的过程中，当遇到坏字符，通过一定的规律，将模式串一次性滑动很多位。

  定义一个数组，用来存储模式串中每个前缀的最长可匹配前缀子串的结尾字符下标，这个数组定义为next数组，也叫失效函数。

  数组下标是每个前缀结束字符的下标，数组的值是前缀的最长可匹配子串的结尾字符下标。

• 时间复杂度分析：

  KMP算法的时间复杂度就是O(m+n)。m是模式串长度，n是主串长度。