# String Matching

在字符串 A 中查找字符串 B，A 叫做**主串**，B 叫做**模式串**。

## BF

Brute Force，暴力匹配算法或朴素匹配算法。

**思想**：主串长度为 n，模式串长度为 m，在主串中，从起始位置 0、1、2 ... n-m 且长度为 m 的 n - m + 1 个子串中，看有没有和模式串匹配的。

最差时间复杂度 O(n\*m)，最差情况下，每次需要对比 m 个字符，需要对比 n - m + 1 次。

{% hint style="info" %}
尽管 BF 算法的时间复杂度很高，但是实际开发中较常用，原因是：

* 大部分情况下，模式串和主串都不太长。
* 每次模式串与主串中的子串比较时，中途遇到不能匹配的，就能提前停止，大部分情况不会达到最差时间复杂度。
* 思想简单，实现简单，不易出错。
  {% endhint %}

## RK

Rabin-Karp 算法，由两位发明者命名的。

BF 算法中，每次模式串与主串的子串比较时，都需要比较模式串的每个字符。RK 的核心思路就是计算 n - m + 1 个子串的 hash 值，然后与模式串的 hash 值比较，hash 的比较就非常快了。

但是所有子串计算 hash 值的时候还是要遍历每个子串的所有字符，此时就需要设计一个 hash 算法来优化。

核心思路是 **hash 值的计算可以利用前一个子串的计算结果**。比如：假设匹配的字符串的字符集只有 K 个字符，可以用 K 进制数来表示一个字符，转换为 10 进制数作为 hash 值。

时间复杂度 O(n)。

如果考虑 hash 冲突，在 hash 值相等后还需要比较原始的字符串。

## BM

Boyer-Moore 算法包含两部分，坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

模式串与主串的匹配过程可以看做是模式串不断在主串中往后移动。当遇到不匹配时，BF、RK 算法是模式串往后移动一位；BM 算法的本质就是寻找规则，让模式串尽可能往后多移动几位。

### 坏字符规则

首先是按照模式串下标从大到小倒着匹配。当发现某个字符（**坏字符**）无法匹配时，坏字符对应模式串中的下标为 si，然后拿这个坏字符在模式串中**从后往前**查找，找到下标为 xi，若没有找到 xi = -1，那么模式串就往后移动 si - xi 位。

如下例子，从后往前匹配，c 是坏字符，si = 2，xi = -1，所以模式串往后移动 3 位。移动完成后接着匹配，a 为坏字符，si = 2，xi = 0，所以模式串往后移动 2 位。

```
a b c a c a b d c
a b d
      a b d
          a b d
```

**最好时间复杂度**：O(n/m)。主串：aaabaaabaaab，模式串：aaaa。

**问题**：主串：aaaaaaaaaaa，模式串：baaa，按照刚才的算法还会后退。

### 好后缀规则

**后缀子串**：最后一个字符对齐，如 abc 的后缀子串有 c、bc。\
**前缀子串**：起始字符对齐，如 abs 的前缀子串有 a、ab。

模式串与主串从后往前比较时，在发现坏字符时，前面已经有部分匹配了，匹配的部分叫做**好后缀**。如下，坏字符为 a，好后缀为 ca。

```
a b c a c a b d c
    d b c a
```

**原理**：模式串已经匹配好的好后缀部分记做 {u}，然后好后缀在模式串中继续查找，找另一个与 {u} 匹配的 {u\*}：

* 若能找到 u{\*}，就将模式串滑动到 {u\*} 与主串中好后缀对齐的位置。
* 若不能找到 u{\*}，就查看**好后缀的后缀子串**是否存在与**模式串的前缀子串**匹配的情况，并找到**最长的 {v}**，然后模式串滑动到 {v} 与主串中 {v} 对齐的部分。

```
// {u} = de，情况 1 能找到 {u*}
a b c d e f g
d e a d e
      d e a d e

// {u} = de，情况 2 不能找到 {u*}，{v} = d
a b c d e f g
e a a d e
        e a a d e
```

{% hint style="info" %}
分别计算好后缀和坏字符规则的滑动长度，取最长的滑动。
{% endhint %}

## KMP

KMP 算法与 KM 本质一样，在模式串与主串匹配过程中，若遇到不匹配的，则寻找规律尽量使模式串多往后移动几位。

## Trie 树

Trie 树，也叫字典树。专门用于处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的问题。

**本质**：利用字符串之间的公共前缀，将重复的前缀合并在一起。

如下图所示，根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的路径表示一个字符串。注意：**红色节点不一定为叶子节点**。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-M0wD0Ry8d11GJcFuMpr%2F-M102AX2K1yeM6L_hlFE%2Fimage.png?alt=media\&token=12dc5209-716c-442c-828f-02b87f4b603e)

```java
// 假设字符串中只有 a~z 26个小写字母。这种存储方式比较消耗内存。
// 节点可以换成其它数据结构来节约内存，比如跳表、散列表、红黑树等
class TrieNode {
  char data;
  TrieNode children[26];
  public boolean isEndingChar = false;
}
```

**时间复杂度**：构建 Trie 树为 O(n)，n 表示所有字符串长度总和，构建仅需一次；查找为 O(k)，k 为需要查找字符串的长度。

**适用条件**：

* 字符集不能太多，不然会消耗很多内存；若节点改成其它数据结构，就会降低效率。
* 字符串前缀重复较多。

**适用场景**：

* 自动不全
* 搜索关键字提示

**与散列表、红黑树比较**：精确匹配适合散列表、红黑树等数据结构；前缀匹配适合 Trie 树。

### 例题

* [LeetCode 208：实现字典树。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT208.java)

## AC 自动机

Aho–Corasick 算法是基于 Trie 树的一种改进算法。