目录

一、字典树

1.插入

2.查询

二、AC自动机

背景知识：

①字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。其基本操作有：查找、插入和删除,当然删除操作比较少见。----百度词条

②复杂度：Trie树其实是一种用空间换时间的算法，它占用的空间很大，但时间是非常高效的，插入和查询的时间复杂度都是O（1）

-------------------------这是一条分割线-------------------------------

下面让我们来看一下算法流程体会一下字典树的算法思想 -------------------------这是一条分割线-------------------------------

如下图所示，这是一个插入字符串为she、he、say、shr、her的字典树（下面的图有点粗糙。。。有人看的话再搞精致一些）

ps:图中root表示根节点,不代表任何字符

接下来是基本操作：

还是上面那幅图

首先，根节点是肯定不存在字符的。

①开始插入吧，首先是she，我们发现根节点的子节点没有存在s，可以插入，s的子节点不存在h，可以插入，h的子节点不存在e，可以插入，如图：

②我们再插入shr，这时候我们发现根节点的子节点存在s，于是可以和他共享这个节点，记住共享这个词，

继续插入h，发现s的子节点已存在h，于是可以继续共享，最后插入r，我们发现h的子节点中没有r这个字符，于是可以插入

最后变成这样

发现了什么性质了吗？

1.我们插入的时候是从根节点的下一层即子节点开始插入的

2.插入字符前，先检查这一层中是否存在同一个字符，若存在，则共享，若不存在，则新建一个子节点