Promacanthus

0.1. 单模式串匹配算法
0.2. 多模式串匹配算法

如果要在字符串 A（长度n）中查找字符串 B（长度m），那么：

主串：A
模式串：B
n>m

0.1. 单模式串匹配算法

0.1.1. BF算法

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

BF 算法的思想在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。极端情况下，算法的时间复杂度是O(n*m)

虽然理论上时间复杂度较高，但在实际开发中挺常用的：

大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，统计意义上，大部分情况下，算法执行效率要比O(n*m)高很多
思想简单、代码简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选（KISS原则）

所以，在实际的软件开发中，绝大部分情况下，朴素的字符串匹配算法就够用了，处理小规模的字符串很好用。

0.1.2. Rk算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。RK 算法是 BF 算法的改进，它巧妙借助了哈希算法，让匹配的效率有了很大的提升。

模式串长度为 m
主串长度为 n
主串中有 n-m+1 个长度为 m 的子串
对比这 n-m+1 个子串与模式串，找出主串与模式串匹配的子串

每次检查主串与子串是否匹配，需要依次比对每个字符，时间复杂度高，引入哈希算法，时间复杂度立刻就会降低。

RK 算法的思路：

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值
逐个与模式串的哈希值比较大小
如果某个子串的哈希值与模式串相等，那就匹配了（先不考虑散列冲突）

哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

但是，通过哈希算法计算子串的哈希值时，需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。

继续改进，优化哈希算法的设计。

假设要匹配的字符串的字符集中只包含 K 个字符，用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。

比如要处理的字符串只包含 a～z 这 26 个小写字母，就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字。

在十进制的表示法中，一个数字的值是通过下面的方式计算出来的：

\[657=6×10^2+5×10^1+7×10^0\]

对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，只需要把进位从 10 改成 26 就可以：

\[cba=c×26^2+b×26^1+a×26^0=2×26^2+1×26+0×1=1353\]

这就是改进后的哈希算法，对应的哈希值就是26进制数转为10进制数后的字面量。这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。

相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。

h[i-1]对应子串s[i,i+m-2]的哈希值 × 26 ==h[i]对应子串s[i,i+m-2]的哈希值
\(h[i]=(h[i-1]-s[i-1]×26^{m-1})×26+s[i+m-1]\)

注意，\(26^{m-1}\) 这部分的计算，可以通过查表的方法来提高效率。

事先计算好 \(26^0\)、\(26^1\)、\(26^2\)……\(26^{m-1}\)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。

需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

0.1.2.1. 时间复杂度

整个 RK 算法包含两部分：

计算子串哈希值：利用上面的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以时间复杂度是 O(n)
模式串哈希值与子串哈希值之间比较：比较操作的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，时间复杂度是O(n)

所以，RK 算法整体的时间复杂度就是 O(n)。

0.1.2.2. 散列冲突

如果模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

RK算法基于进制来表示一个字符串的，这样的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。

实际上，为了能将哈希值落在整型数据范围内，可以牺牲一下，允许散列冲突。如上面的哈希算法不基于进制求字符串，而是将每一个字符求和作为字符串的哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多了，但是冲突概率也就高很多。

稍微优化一下，将每一个字母从小到大对应一个素数，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。

当存在散列冲突后，哈希值虽然是相同，但是两者本身并不匹配，此时再对比一下子串和模式串本身就好了。

所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。

0.1.3. BM算法

BM（Boyer-Moore）算法是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。

BM 算法，本质上就是在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

BM 算法包含两部分，分别是：

坏字符规则（bad character rule）
好后缀规则（good suffix shift）

0.1.3.1. 坏字符规则

BF与RK算法在匹配的过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的
BM 算法的匹配顺序是按照模式串下标从大到小的顺序，倒着匹配的

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

当遇到坏字符发生不匹配时，把坏字符对应的模式串中的字符下标记作 si
如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi
如果不存在，把 xi 记作 -1

那模式串往后移动的位数就等于 si-xi，注意，这里说的下标，都是字符在模式串的下标。

注意：如果坏字符在模式串里多处出现，在计算 xi 时，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 \(O(n/m)\)。

只使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。

0.1.3.2. 好后缀规则

好后缀规则跟坏字符规则的思路很类似。从模式串的末尾往前倒着匹配，把已经匹配的字符串叫作好后缀，记作{u}。

拿{u}在模式串中查找
如果找到了另一个跟{u}相匹配的子串{u*}，就将模式串滑动到子串{u*}与主串中{u}对齐的位置
如果找不到另一个等于{u}的子串，那一步步滑动模式串，当模式串滑动到前缀与主串中{u}的后缀有部分重合，并重合的部分相等时，就有可能会存在完全匹配的情况
针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的
从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置

所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc
所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab

当模式串和主串中的某个字符不匹配的时候，分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这可以避免根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。

0.1.3.3. 实现过程优化

坏字符规则：

当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的计算是重点。

如果拿坏字符，在模式串中顺序遍历查找，这样算法的性能较低，可以使用散列表进行优化
将模式串中的每个字符及其下标都存到散列表中。这样就可以快速找到坏字符在模式串的位置下标

假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。

好后缀规则：

好后缀规则中最核心的内容：

在模式串中，查找跟好后缀匹配的另一个子串
在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串

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

后缀子串：

后缀子串的最后一个字符的位置是固定的，下标为 m-1，只需要记录后缀子串的长度，通过长度，可以确定一个唯一的后缀子串。

引入变量 suffix 数组：

数组的下标 k：表示后缀子串的长度
下标对应的数组值存储的是：在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值

如果模式串中有多个子串跟后缀子串{u}匹配，那 suffix 数组中存储模式串中最靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。

还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。引入boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

计算并填充这两个数组：拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，就记录 prefix[k]=true。

在模式串跟主串匹配的过程中，遇到不能匹配的字符时，根据好后缀规则，计算模式串往后滑动的位数。

假设好后缀的长度是 k。先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。

好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。

如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，就将整个模式串后移 m 位。

0.1.3.4. 性能分析

内存消耗，整个算法用到了额外的 3 个数组，其中：
- bc 数组的大小跟字符集大小有关（如果运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗）
- suffix 数组和 prefix 数组的大小跟模式串长度 m 有关
执行效率：基于当前版本，在极端情况下，预处理计算 suffix 数组、prefix 数组的性能会比较差。比如模式串是 aaaaaaa 这种包含很多重复的字符的模式串，预处理的时间复杂度就是 \(O(m^2)\)。只使用好后缀规则的 BM 算法效率会下降一些。

0.1.4. KMP算法

KMP 算法跟 BM 算法的本质是一样的，全称是 Knuth Morris Pratt 算法。

在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。

当遇到坏字符的时候，把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。

KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？

只要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，就把 j 更新为 k，i 不变，然后继续比较。

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

KMP 算法提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。把这个数组定义为 next 数组，或者叫失效函数（failure function）。

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

0.2. 多模式串匹配算法

搜索引擎的搜索关键词提示功能，底层最基本的原理就是Trie 树这种数据结构。

与单模式匹配算法相比，多模式匹配算法只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。

0.2.1. Trie树

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

字符串匹配问题也可以用：散列表、红黑树，或者上面的字符串匹配算法来解决，但是，Trie 树在这个问题的解决上，有它特有的优点。

假设有6个字符串：how，hi，her，hello，so，see，需要在里面多次查找某个字符是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那就太没有效率了。

先对这 6 个字符串做一下预处理，组织成 Trie 树的结构
每次查找，都是在 Trie 树中进行匹配查找。

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

最后构造出如下图所示的Trie树：

根节点不包含任何信息
每个节点表示一个字符串中的字符
从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）

具体的Trie树构造过程如下图所示，相当于往Trie树中插入一个字符串，当所有字符串插入完成，Trie树就构造好了。

当在 Trie 树中查找一个字符串时：

查找字符串“her”，
将要查找的字符串分割成单个的字符 h，e，r，
从 Trie 树的根节点开始匹配。

如下图所示，绿色的路径就是在 Trie 树中匹配的路径。

查找字符串“he”
拆分单词
从根节点开始，沿着某条路径来匹配

如下图所示，绿色的路径，是字符串“he”匹配的路径。但是，路径的最后一个节点“e”并不是红色的。也就是说，“he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。

0.2.1.1. 实现Trie树

Trie 树主要有两个操作：

将字符串集合构造成 Trie 树（将字符串插入到 Trie 树的过程）
在 Trie 树中查询一个字符串

Trie 树是一个多叉树，经典的存储方式，借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针，如下图所示。

假设字符串中只有从 a 到 z 这 26 个小写字母
数组中下标为 0 的位置，存储指向子节点 a 的指针
数组中下标为 1 的位置，存储指向子节点 b 的指针
以此类推
数组中下标为 25 的位置，存储的是指向的子节点 z 的指针
如果某个字符的子节点不存在，在对应的下标的位置存储 nil

type TrieNode struct {
 data     rune
 children [26]*TrieNode
}

在 Trie 树中查找字符串时，通过字符的 ASCII 码减去“a”的 ASCII 码，迅速找到匹配的子节点的指针。

0.2.1.2. 时间复杂度

如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）
构建成功后，后续的查询操作会非常高效
每次查询时，如果要查询的字符串长度是 k，只需要比对大约 k 个节点，就能完成查询操作，跟原本那组字符串的长度和个数没有任何关系

构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

0.2.1.3. 空间复杂度

Trie 树是一种非常独特的、高效的字符串匹配方法（空间换时间），在实现的时候，用数组来存储一个节点的子节点的指针。

假设字符串中只有从 a 到 z 这 26 个小写字母
节点都要存储一个长度为26的数组
每个数组元素包含一个字符（4字节）和一个指针（1字节）
因此，每个节点26×5byte=130byte

如果字符串中不仅包含小写字母，还包含大写字母、数字、甚至是中文，那需要的存储空间就更多了。

Trie 树的本质是避免重复存储一组字符串的相同前缀子串，但是，在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

0.2.1.4. 空间优化

可以稍微牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点的子节点指针。比如：

有序数组：数组中的指针按照所指向的子节点中的字符的大小顺序排列，查询的时候，使用二分查找的方法，在插入数据时，维护数组有序性会导致效率降低
跳表
散列表
红黑树

Trie 树的变体有很多，都可以在一定程度上解决内存消耗的问题。比如，缩点优化：

对只有一个子节点的节点
而且此节点不是一个串的结束节点
可以将此节点与子节点合并

这样可以节省空间，但却增加了编码难度。

0.2.1.5. Trie 树与散列表、红黑树的比较

字符串的匹配问题，其实就是数据的查找问题。

对于支持动态数据高效操作的数据结构，比如散列表、红黑树、跳表等，也可以实现在一组字符串中查找字符串的功能。

在上面的场景中，在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。

第一，字符串中包含的字符集不能太大（如果字符集太大，那存储空间可能就会浪费很多即便可以优化，但也要付出牺牲查询、插入效率的代价）
第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多
第三，如果要用 Trie 树解决问题，就要从零开始实现一个 Trie 树，还要保证没有 bug（这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做）
第四，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综合这几点，针对在一组字符串中查找字符串的问题，在工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，不需要自己去实现，直接利用编程语言中提供的现成类库就行了。

Trie 树不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决
Trie 树适合前缀匹配查找，比如自动输入补全（搜索栏，IDE代码、浏览器地址、命令行、输入法）

0.2.2. AC自动机

0.2.2.1. 场景：敏感词过滤

对敏感词字典进行预处理，构建成 Trie 树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，只需要动态更新一下 Trie 树。
当用户输入一个文本内容后，把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。
当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。

基于 Trie 树的这种处理方法，有点类似单模式串匹配的 BF 算法。

单模式串匹配算法中，KMP 算法对 BF 算法进行改进，引入了 next 数组，让匹配失败时，尽可能将模式串往后多滑动几位。
借鉴单模式串的优化改进方法，对多模式串 Trie 树进行改进，进一步提高 Trie 树的效率，这就要用到 AC 自动机算法。

0.2.2.2. 构建AC自动机

AC 自动机算法，全称是 Aho-Corasick 算法。

Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只是针对的是多模式串。

AC 自动机是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上。

AC 自动机的构建，包含两个操作：

将多个模式串构建成 Trie 树
在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）

构建好 Trie 树之后，如何在它之上构建失败指针？如下示例：有 4 个模式串，分别是 c，bc，bcd，abcd；主串是 abcd。

Trie 树中的每一个节点都有一个失败指针，它的作用和构建过程，跟 KMP 算法中的 next 数组极其相似。

假设沿 Trie 树走到 p 节点（下图中的紫色节点），那 p 的失败指针就是从 root 走到紫色节点形成的字符串 abc
与所有模式串前缀匹配的最长可匹配后缀子串，就是箭头指的 bc 模式串

最长可匹配后缀子串：字符串 abc 的后缀子串有两个 bc，c，拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，就把这个后缀子串叫作可匹配后缀子串。从可匹配后缀子串中，找出最长的一个，就是最长可匹配后缀子串。

将 p 节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点，就是下图中箭头指向的节点

计算每个节点的失败指针：把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。

像 KMP 算法那样，当求某个节点的失败指针时，通过已经求得的、深度更小的那些节点的失败指针来推导。

可以逐层依次来求解每个节点的失败指针。所以，失败指针的构建过程，是一个按层遍历树的过程。

首先 root 的失败指针为 NULL，也就是指向自己
当已经求得某个节点 p 的失败指针之后，寻找它的子节点的失败指针
1. 假设节点 p 的失败指针指向节点 q，看节点 p 的子节点 pc 对应的字符，是否也可以在节点 q 的子节点中找到
2. 如果找到了节点 q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc

如果节点 q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指针）
继续上面的查找，直到 q 是 root 为止
如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root

通过按层来计算每个节点的子节点的失效指针，最后构建完成之后的 AC 自动机就是下面这个样子：

0.2.2.3. 匹配AC自动机

AC 自动机构建完成后，在 AC 自动机上匹配主串。

在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。

如果 p 指向的节点有一个等于 b[i]的子节点 x，就更新 p 指向 x，这个时候通过失败指针，检测一系列失败指针为结尾的路径是否是模式串
处理完之后，将 i 加一，继续这两个过程
如果 p 指向的节点没有等于 b[i]的子节点，那失败指针就派上用场了，让 p=p->fail，然后继续这 2 个过程

0.2.2.4. 时间复杂度

Trie树构建的时间复杂度是O(m*len)，len表示敏感词的平均长度，m表示敏感词的个数

假设 Trie 树中总的节点个数是 k，每个节点构建失败指针的时候，最耗时的环节是 while 循环中的 q=q->fail，每运行一次这个语句，q 指向节点的深度都会减少 1，而树的高度最高也不会超过 len，所以每个节点构建失败指针的时间复杂度是 O(len)。整个失败指针的构建过程就是 O(k*len)。

for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 O(len)，所以总的匹配的时间复杂度就是 O(n*len)。

因为敏感词并不会很长，时间复杂度可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。

实际上，因为失效指针可能大部分情况下都指向 root 节点，所以绝大部分情况下，在 AC 自动机上做匹配的效率要远高于上面理论的时间复杂度。只有在极端情况下，如图所示，AC 自动机的性能才会退化的跟 Trie 树一样。

17 字符串匹配