要抹去懊悔，终究只有继续不断努力。——《樱花庄的宠物女孩》

字典树

字典树（Trie Tree） 是一个比较简单的数据结构，也叫前缀树，用来存储和查询字符串。例如， 这几个单词可以用以下方式存储：

我是一棵字典树！

其中每个字符占据一个节点，拥有相同前缀的字符串可以共用部分节点。

字典树的食用

建树

起始点是特殊点（我们设为 号点），不存储字符，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MAXN = 1e5 + 5;
int nxt[MAXN][26]; // 用类似前向星的方式存图，nxt[i][c] 表示 i 号点所连，存储字符为 c + 'a' 的节点
void init () // 初始化 
{
	memset (nxt, 0, sizeof (nxt));
	cnt = 1; // 编号从 1 开始，但是这个点不存 
}
inline void insert (const string &s) // 插入字符串 
{
	int cur = 1; // 是个指针，存当前编号
	for (auto c : s) // 遍历字符串（要使用 auto ，请将版本换为 c++11 ） 
	{
		if (!nxt[cur][c - 'a']) // 如果不存在这个节点 
			nxt[cur][c - 'a'] = ++ cnt; // 创造一个新节点 
		cur = nxt[cur][c - 'a']; // 继续向下 
	} 
}

查询

字典树可以方便的查询某个前缀是否已经存在：

1
2
3
4
5
6
7
8
9
10
11
12
13
inline bool find_prefix (const string &s) // 查询前缀
{
	int cur = 1; // 定义光标为 1
	for (auto c : s) // 遍历字符串 
	{
		// 沿着前缀决定的路向下走，如果中途发现某个节点不存在，说明前缀不存在  
		if (!nxt[cur][c - 'a']) // 如果不存在 
			return false; // 返回假 
		cur = nxt[cur][c - 'a']; 
	}
	
	return true; // 最后如果一直存在，就返回真 
}

如果是查询某个字符串是否存在，可以另开一个 数组，在插入完成时，把 设置为 ， 然后先按查询前缀的方法查询，在结尾处再判断一下 的值，用叶子节点代表整个字符串，保存某些信息。

字典树是一种用空间换时间的数据结构，牺牲了字符串个数 字符串平均字符数 字符集大小的空间，但可以用 的时间查询，其中 为查询的前缀或字符串的长度。