基本的字典树

字典树是一种支持快速插入、查询字符串以及查找字符串插入次数的多叉树结构，其根节点编号为 $0$，其他节点标识路径，边表示字符。

需要以下组件：

• trie[i][j]：存储从结点 $i$ 沿着边 $j$ 走到的子节点编号，其中 $j$ 取值为 $[0,25]$，代表字符
• end[i]：存储以结点 $i$ 结尾的单词的插入次数
• idx：用于给节点编号
• pass[i]：存储经过节点 $i$ 的次数

插入

const int N = 1e6;
int trie[N][26], pass[N], end[N], idx = 1;
void insert(string s) {
	int k = 1; // 根节点开始
	pass[k]++; // 根节点肯定被经过
	for (int i = 0; i < s.length(); i++) {
		int j = s[i] - 'a'; // 建立字母映射
		if (!trie[k][j]) trie[k][j] = ++idx; // 若结点不存在，则创建一个新的
		k = trie[k][j]; // 往下走
		pass[k]++;
	}
	end[k]++; // 结尾给单词计数器加 1
}

查询

查询某个字符串是否存在及出现次数

从根节点开始查，若字母存在则沿这条字母的边走下来，走到结尾则返回插入次数；若字母不存在则返回 $0$.

int query(string s) {
	int k = 1;
	for (int i = 0; i < s.length(); i++) {
		int j = s[i] - 'a';
		if (!trie[k][j]) return 0; // 没路走，说明没加过这个单词，直接返回 0
		k = trie[k][j]; // 往下走
	}
	return end[k];
}

查询以某字符串为前缀的字符串的个数

int queryPrefix(string s) {
	int k = 1;
	for (int i = 0; i < s.length(); i++) {
		int j = s[i] - 'a';
		if (!trie[k][j]) return 0; // 没路走，说明不是任何一个已添加字符串的前缀，直接返回 0
		k = trie[k][j]; // 往下走
	}
	return pass[k];
}

删除