前言：算法第三弹笔记来袭！主要内容为Trie树及AC自动机。

Trie树

（1）Trie树：也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
（2）Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。
（3）在 Trie 树中，查找某个字符串的时间复杂度是多少。扫描所有的字符串，时间复杂度是O(n)（n 表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。
（4）Trie 树内存消耗问题：耗内存。
优化方案：可以稍微牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点的子节点指针。用哪种数据结构呢？我们的选择其实有很多，比如有序数组、跳表、散列表、红黑树等。
实际上，Trie 树的变体有很多，都可以在一定程度上解决内存消耗的问题。比如，缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。这样可以节省空间，但却增加了编码难度。
（5）Trie 树与散列表、红黑树的比较
第一，字符串中包含的字符集不能太大。
第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
第三，如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树。
第四，通过指针串起来的数据块是不连续的。
结论：实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串，也就是类似开篇问题的那种场景。
（6）Trie树可用于实现搜索引擎的搜索关键词提示功能

AC自动机

（1）多模式串匹配算法：
对敏感词字典进行预处理，构建成 Trie 树结构。如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那我们只需要动态更新一下 Trie 树就可以了。当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。
（2）经典的多模式串匹配算法：AC 自动机
AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。
AC 自动机的构建，包含两个操作：将多个模式串构建成 Trie 树；在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。
（3）将敏感词构建成 AC 自动机，包括构建 Trie 树以及构建失败指针。AC 自动机做匹配的时间复杂度近似于 O(n)。
（4）AC自动机可用于多模式串匹配实现敏感词过滤功能