文章目录
前言
一、Trie
二、例题，代码
1.AcWing 835. Trie字符串统计
关于本题：
AC代码
2.AcWing 143. 最大异或对
关于本题
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Trie，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、Trie
能高效的插入和查找字符串的数据结构 -------yxc
我们通过一个例子来说明什么是Trie：
例如，现我们要存储这么几个字符串：
abcdef
abedf
acef
cbde
cbdf
abc
我们按照如下方式存储：
首先我们定义一个树根：
然后把树根的初始坐标设为0，紧接着我们开始例子的插入操作：
插入abcdef
询问树根是否有a这个子节点，如果没有，则创建：
然后看a这个子节点有没有b这个子节点，如果没有则创建，剩下的也以此类推，所以插入abcdef后的图如下图所示：
紧接着我们插入abedf
还是从root开始，看有没有a的子节点，发现有，那么就就走到a这个子节点
接下来看有没有b这个字节点，发现有，那么走到b这个子节点
接下来看有没有e这个字节点，发现没有，那么创建这个子节点
接下来和之前的一样，创建d子节点和f子节点
接下来插入acef，和之前一样，插入后结果为
接下来cbde，一样从root开始，发现没有c子节点，则创建
接下来插入cbdf，和之前一样，最终结果为
插入abc
我们还需要一个操作就是标记一下每一个插入的串的结尾，这样我们做查询操作的时候才能知道到底有没有这个串，比如，如果我们不标记一下结尾的话，那么对于我们插入abc这个串的时候，我们这个Trie树种已经有abc这个子串了，那么我们如果要查询是否有abc这个子串的时候，我们才能知道是真的有这个串，而不是abcdef的子串，故我们标记为：
从这个表中，我们就储存了所有的字符串，并且标记了每一个串的结尾，那么我们在查询的时候从root开始遍历到这个标记的结尾的话，就证明存在这个子串
