前言

距离 2026 CSP 还有 3 天。

只会模板。

字典树

正如一个字典一样。字典树按照字典序来存字符串。每个节点都可以有字符集那么多个子节点。虽然实际上不会有那么多。

例如这些字符构造字典树，$\texttt{apple},\texttt{cat},\texttt{car},\texttt{dog},\texttt{algorithm},\texttt{duck}$ 如图：

这样就能存所有字符了。而且还需要知道：以这个字符结尾有多少个字符串。比如两个相同的 $\texttt{dog}$ 单词，那么在 $\texttt{d}\to\texttt{o}\to\texttt{g}$ 的 $\texttt{g}$ 节点，就有 $2$ 个字符串。可以定义结构体：

struct fu
{
	int nxt[128];
	int cnt;
}tre[N];
int tot;

nxt 开字符集的大小会合适一点。实在不行的话，就无脑开 $128$。

对了 $N$ 是字符串总长度，不是单个长度。因为每个字符都要一个格子。

插入

遍历一个字符串。如果当前的位置没有节点就新建。然后到新的位置。

void update(string str)
{
	int u = 0;
	for (char ch : str)
	{
		int v = ch;
		if (!tre[u].nxt[v])
			tre[u].nxt[v] = ++tot;
		u = tre[u].nxt[v];
	}
	++tre[u].cnt; //
}

注释那里具体要根据题目改变。

查询

一样的思路。空时和结束时返回相应的内容。

int que(string str)
{
	int u = 0;
	for (char ch : str)
	{
		int v = ch;
		if (!tre[u].nxt[v])
			return 0;
		u = tre[u].nxt[v];
	}
	return tre[u].cnt;
}

像这里就是查询与 $str$ 相等的字符串个数。