字典树Trie

字典树是我感觉为数不多的懂算法比写代码简单的东西了。

字典树是解决多组字符串匹配的问题的数据结构。

过程类似查字典，是先找每个单词的首字母，在找第二个，以此类推。

在建树的过程中，每一个单词，先遍历这个单词，把这个单词放到树上，就是一个如果它的首字母有，就向下看有没有第二个，以此类推，如果有，就新建节点。 值得注意的是，在建树的过程中，每一个单词的结尾都要打上标记，这样才可以统计。

建完树之后，就是查找部分。

查找就是顺着这个树向下爬，如果不匹配，就直接返回，匹配就继续向下爬。 最后返回最后的节点的标记数。

定义 $son_{p,u}$ 代表第 $p$ 个节点的 $u$ 个儿子是谁。$cnt_p$ 表示以节点 $p$ 结尾的单词有多少个。$idx$ 表示节点数量。

刚开始先定义一个 $p$ 表示当前位置的指针。 遍历字符串，将当前字符 $c$ 映射成一个整数 $u$，可以得出 $son_{p,u}$ 是节点 $p$ 对于 $u$ 的路。 如果 $son_{p,u}$ 是没有值得，那么说明是没有这个点的，那么将节点数 $idx$ 加 $1$，让后给 $son_{p,u}$ 标记编号 $idx$。 标完节点之后，让 $p$ 跳到下一个节点 $son_{p,u}$ 就行了。 在遍历完单词之后，$p$ 跳到了最后一个节点，所以给 $p$ 这个节点标记，也就是 $cnt_p$ 加 $1$。

查询和建树基本一样，只是在 $son_{p,u}$ 没有值的时候直接返回 $0$，因为单词前缀断了就不可能匹配。 最后返回 $cnt_p$，也就是记录的次数。

字典树可以通过修改 $cnt$ 数组的含义来实现其他功能。

时间复杂度 $O(len)$，即字符串长度，空间复杂度好像是 $O(n|\Sigma|)$，其中 $n$ 为节点个数，$|\Sigma|$ 是字符集大小。 貌似使用哈希表可以做到 $O(n)$ 空间。

注意点 1.$son$ 数组的第一维要开 $\sum len$，也就是所以字符串的长度之和。 2.多测时清空 $son$ 数组和 $cnt$ 要手动清空，只用清空前 $idx$ 个就可以了。 3.注意题目中的字符映射，不一定只是小写字母。因此，也要注意 $son$ 数组的第二维开多大。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt[N];
int son[N][30];
int idx;
int n,m;
char s[N];
void insert(char c[]){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!son[p][x])son[p][x]=++idx;
		p=son[p][x];
	}
	cnt[p]++;
}
int query(char c[]){
	int p=0;
	for(int i=0;c[i];i++){
		int x=c[i]-'a';
		if(!son[p][x])return 0;
		p=son[p][x];
	}
	return cnt[p];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		insert(s);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%s",s);
		cout<<query(s)<<'\n';
	}
	return 0;
}