Skip to main content

字典树

Summary

字典树（Trie，前缀树）把字符串集合按公共前缀组织成一棵树：从根到某节点的路径对应一个前缀，每条边代表一个字符。插入与查询一个长度为 L 的串都是 O(L)，与集合大小无关。它常用于前缀检索、词频统计，也能配合异或贪心解决最大异或对一类问题。实现给出一个用二维数组存转移的结构体，支持初始化、插入与查询前缀出现次数。

参考资料​

简介​

字典树（Trie），又称前缀树，把字符串集合按公共前缀组织成一棵树：从根到某节点的路径对应一个前缀，每条边代表一个字符。插入与查询一个长度为 LL 的串都是 O(L)O(L)，与集合大小无关。常用于前缀检索、词频统计，以及配合异或贪心解决最大异或对等问题。

实现​

395 Bcpp
struct Trie
{
	int T[N][M],val[N];
	int cnt=0;
	void init()
	{
		for(int i=0;i<=cnt;i++)
		{
			memset(T[i],0,sizeof T[i]);
			val[i]=0;
		}
		cnt=0;
	}
	void insert(string s)
	{
		int u=0;
		for(auto c:s)
		{
			int &v=T[u][c];
			if(!v)v=++cnt;
			val[u=v]++;
		}
	}
	int query(string s)
	{
		int u=0;
		for(auto c:s)
		{
			int v=T[u][c];
			if(!v)return 0;
			u=v;
		}
		return val[u];
	}
};

例题​

洛谷 P8306 【模板】字典树

给定 nn 个模式串 s1,s2,…,sns_1, s_2,\dots, s_n 和 qq 次询问，每次询问给定一个文本串 tit_i，请回答 s1∼sns_1\sim s_n 中有多少个字符串 sjs_j 满足 tit_i 是 sjs_j 的 前缀。

一个字符串 tt 是 ss 的前缀当且仅当从 ss 的末尾删去若干个（可以为 0 个）连续的字符后与 tt 相同。