前缀字典树trie树的定义
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
trie树的应用
（1）统计前缀出现的次数
这是Trie最基本的应用，每个结点的字母使用count记录出现的次数即可。
（2）翻译（密码，明文）
给定一组字符串s，k我们输入k则需要翻译成s，也就是说两者是映射关系。接下来我们给出一段话，让你翻译出正常的文章。用map固然简便，但是Trie的效率更加高。只需要在k的结尾结点出记录下s即可。
（3）实现搜索引擎的热门搜索排名
将字符串和出现次数存进一个结构体，最后对这个数组进行排序，看网上说可以利用分治+trie+最小堆
（4）输入自动补全
其实原理都差不多，把字符串结尾处的结点当作root，进行先序遍历，即可得出所有以输入的字符串为前缀的答案。
后缀字典树
简介
后缀树，它描述了给定字符串的所有后缀，许多重要的字符串操作都能够在后缀树上快速地实现。
一个长度为n的字符串S，它的后缀树定义为一棵满足如下条件的树：
- 从根到树叶的路径与S的后缀一一对应。即每条路径惟一代表了S的一个后缀；
- 每条边都代表一个非空的字符串；
- 所有内部节点（根节点除外）都有至少两个子节点。
由于并非所有的字符串都存在这样的树，因此S通常使用一个终止符号进行填充（通常使用$）。
优点
匹配快。对于长度为m的模式串，只需花费至多O(m)的时间进行匹配。
空间省。Suffix tree的空间耗费要低于Suffix trie，因为Suffix tree除根节点外不允许其内部节点只含单个子节点，因此它是Suffix trie的压缩表示。
应用
后缀树（Suffix tree）是一种树形数据结构，能快速解决很多关于字符串的问题。后缀樹的概念最早由Weiner 於1973年提出，既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改進完善。
总结起来，它主要可以解决类似如下的一些问题：
- 查找字符串o是否在字符串S中
- 指定字符串T在字符串S中的重复次数
- 字符串S中的最长重复子串
- 两个字符串S1，S2的最长公共部分
这些问题如何解决，我们最后再谈。
查找字符串o是否在字符串S中
解法：如果S存在于o中，那么S必然是o的某一个后缀的前缀，按照Trie树搜索前缀的方法，遍历后缀树即可。复杂度为O(M)，其中M为字符串S的长度。 原理：若o在S中，则o必然是S的某个后缀的前缀。 例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。
指定字符串T在字符串S中的重复次数
解法：在字符串S后追加$构造包含所有后缀的完整后缀树，在其中找到T子川，的最后一个节点，该节点拥有的叶子节点个数几位重复次数，复杂度为O(M)，M为T的长度。 原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。
字符串S中的最长重复子串
解法：遍历整个后缀树，找到深度最大的非叶子节点，复杂度为O(N)，N为字符串的长度。 这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。 为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。
两个字符串S1，S2的最长公共部分
解法：分别 为S1、S2追加#、$作为末尾，把他们压入同一个后缀树，然后找到最深的非叶子节点，该节点的叶子节点中，既有#又有$。复杂度为构造两颗后缀树的复杂度之和，取最大即可max(O(N),O(M))，其中N、M为S1、S2的长度，假设我们以线性时间构造了后缀树，下位讲解构造方法。 方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。
模板
class TrieNode:
def __init__(self):
self.precount = 0
self.count = 0
self.children = {}
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.precount += 1
node.count += 1
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.count > 0
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return node.precount > 0
trie可以用来求最大异或值。
参考下面：
找最长公共前缀
- 100268. 最长公共后缀查询 字典树题目，字典树节点上额外维护最小长度的string index，这样search这个Trie树时可以直接返回这个index。
下面这个已落后，废弃
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
cur = self.trie
for w in word:
if w not in cur:
cur[w] = {}
cur = cur[w]
cur["#"] = 1
return
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
cur = self.trie
for w in word:
if w not in cur:
return False
cur = cur[w]
return "#" in cur
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
cur = self.trie
for w in prefix:
if w not in cur:
return False
cur = cur[w]
return len(cur.keys()) > 0