字典树

字典树是我接触自动机的开端，我们先讲自动机，

自动机

自动机有五个要素，开始状态，转移函数，字符集，状态集，结束状态。

自动机识别字符串

假设我们有一个自动机，他长这个样子,他能识别字符串abc.
稍等片刻！下图正在转码中

1
2
3
4

graph LR
start((start))--a--> 1((1))
1((1))--b-->2((2))
2((2))--c-->3((end))

最开始我们在位置start，也就是初始状态，当我们读入字符a的时候，经过转移函数我们到达了1号状态，如果我们在初始状态读到的是字符b，则因为初始状态没有字符b的转移函数。会导致自动机在非终结状态停机，这就意味着无法识别字符b，同理也无法识别c-z,于是在初始状态只能识别a，

然后分析状态1，只能识别b，到达状态2，只能识别c到达终态。最后就识别了字符串abc。

然后我们来考虑一个复杂一点的自动机，他能识别字符串abc、abd、bc、ac

稍等片刻！下图正在转码中

1
2
3
4
5
6
7
8

graph TB
start((start))--a--> 1((1))
1((1))--c-->10((end))
start((start))--b--> 3((3))
3((3))--c--> 10((end))
1((1))--b-->2((2))
2((2))--c-->10((end))
2((2))--d-->10((end))

如果我们不去分析其中的end节点，他的本质就是一颗树，他同时又叫做字典树，特别的，如果这个字典树的字符集为01，则他又叫做01字典树。

字典树的插入

字典树的插入应该是一个字符串，这个过程我们可以用递归实现，

字典树的删除

特别注意，为了能够支持多重集合，我们常常用一个数字来代表有多少个字符串在某个状态结束，这样删除的时候只要减少那个值就可以了

字典树的查找

递归。

递归转非递归

因为字典树的代码特别简单，我们常常直接用递归转非递归来实现。

代码

先欠着，暂时拖一个不太友好的代码在这里,这里面有一部分代码就是字典树啦。
代码链接