# 字符串匹配

* `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`是主串长度。
