字典树

参考资料

• 字典树 (Trie) - OI Wiki

简介

字典树（Trie），又称前缀树，把字符串集合按公共前缀组织成一棵树：从根到某节点的路径对应一个前缀，每条边代表一个字符。插入与查询一个长度为 $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 【模板】字典树

给定 $n$ 个模式串 $s_1, s_2,\dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1\sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的 前缀。

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