# 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 树，也叫字典树。专门用于处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的问题。

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

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

![](/files/-M102AX2K1yeM6L_hlFE)

```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 树的一种改进算法。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/string-matching.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.