字典树（Trie）

实现

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 f:s)
		{
			int &v=T[u][f];
			if(!v)v=++cnt;
			u=v;
			val[u]++;
		}
	}
	int query(string s)
	{
		int u=0;
		for(auto f:s)
		{
			int v=T[u][f];
			if(!v)return 0;
			u=v;
		}
		return val[u];
	}
};

例题

洛谷 P8306 【模板】字典树

洛谷 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$ 相同。

Reference Code

#include <bits/stdc++.h>
using namespace std;

const int N=3000005;
const int M=128;
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 f:s)
	{
		int &v=T[u][f];
		if(!v)v=++cnt;
		u=v;
		val[u]++;
	}
}
int query(string s)
{
	int u=0;
	for(auto f:s)
	{
		int v=T[u][f];
		if(!v)return 0;
		u=v;
	}
	return val[u];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,q;
		cin>>n>>q;
		for(int i=1;i<=n;i++)
		{
			string s;
			cin>>s;
			insert(s);
		}
		while(q--)
		{
			string s;
			cin>>s;
			cout<<query(s)<<'\n';
		}
		init();
	}
	return 0;
}