小编点评

**Aho-Corasick 算法 AC自动机实现** **双数组 Trie 树** (Double-array Trie)： * 双数组结构，其中第一个数组存储字符串的指针。 * 第二个数组存储字符串本身。 * 每个节点包含一个字符串的指针。 * 每个节点的子节点包含该节点对应字符串的所有子节点的字符。 **字典树** (Prefix Tree)： * 每个节点只包含一个字符的指针。 * 每个节点对应一个字符串。 * 每个节点的子节点包含该节点对应字符串的所有子节点的字符。 * 每个节点都包含所有字符串的公共前缀。 **优点和缺点** **Trie 树**： * 利用字符串的公共前缀来减少查询时间。 * 每个字符可能包含多个字符集大小数目的指针。 * 空间效率高，当字符串较多时，会有大量的空节点。 **双数组 Trie 树**： * 每个字符的指针指向对应字符串的第一个字符。 * 每个节点包含所有字符串的子节点的字符。 * 存储效率更高，空间复杂度降低。 **应用场景** * **单词自动补齐**：输入字符串的前缀，查找包含该前缀的所有字符串。 * **字符串集合维护**：向集合中插入字符串，查询集合中是否存在某个字符串。 * **字符串搜索**：查询字符串集合中是否有某个字符串。 * **统计字符串出现频率**：统计字符串在集合中的出现频率。 * **字典序排序**：排序字符串集合按字典序。 * **求集合内两个字符串的 LCP**：求最长公共前缀。

正文

Aho-Corasick 算法 AC自动机实现：https://www.cnblogs.com/vipsoft/p/17722761.html
双数组Trie树 (Double-array Trie)：https://www.cnblogs.com/vipsoft/p/17759850.html

Trie树，又叫字典树，前缀树(Prefix Tree)，单词查找树，是一种多叉树的结构.

{"a","apple","appeal","appear","bee","beef","cat"} 深色表示接受态

关键字集合{"pool", "prize", "prepare", "preview", "produce", "progress"}.

Trie 树举例
原字符串集合：{ abcde 、aced 、bcdf 、bcff }
插入字符串：aced 、cdaa
新字符串集合：{ abcde 、abde、aced 、bcdf 、bcff 、cdaa }

字典树的基本性质如下：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同.

Trie 树的优缺点
Trie 树是一种 以空间换时间 的数据结构。

• 优点：利用字符串的 公共前缀 来减少查询时间，最大限度地减少无谓的字符串比较。

  公共前缀：例如字符串 abcdef 与 abcghi 有公共前缀 abc 。

• 缺点：其每一个字符都可能包含至多字符集大小数目的指针。

在本模板采用子结点默认包含 所有字符集 的连接方式，
对于少量的字符串存储来说，大量的结点的儿子是空闲的，造成了 空间的浪费 。

当我们在浏览器的搜索框中打出一个字符串的前缀时，它便实时的显示出了以这个输入为前缀的一些字符串，也就是说，它帮我们搜索到了以这个输入为前缀的所有字符串，并且显示出了搜索频率较高的一些，这就是字典树的一个应用场景：单词自动补齐.

输入“人工” 自动带出人工开头的关键字

应用场景

• 1、维护字符串集合（即字典）。
• 2、向字符串集合中插入字符串（即建树）。
• 3、查询字符串集合中是否有某个字符串（即查询）。
• 4、统计字符串在集合中出现的个数（即统计）。
• 5、将字符串集合按字典序排序（即字典序排序）。
• 6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。