基础知识  

---

一 . 定义

字典树（TrieTree），是一种树形结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串，如01字典树）。字典树主要包含两种操作，插入和查找，删除也可以完成，但是用得比较少。

主要思想：利用字符串的公共前缀来节约存储空间。树中的边来代表有无字符以及是哪个字符，每个节点存储的信息有是否为单词结尾以及后续字符是什么。很好地利用了串的公共前缀，节约了存储空间。

Trie 树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

---

模板题：洛谷 P8306 【模板】字典树

题目描述

给定 n 个模式串 s1​,s2​,…,sn​ 和 q 次询问，每次询问给定一个文本串 ti​，请回答s1​∼sn​ 中有多少个字符串 sj​ 满足 ti​ 是 sj​ 的前缀。

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

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数，表示数据组数 T。

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 n 和询问的个数 q。
接下来 n 行，每行一个字符串，表示一个模式串。
接下来 q 行，每行一个字符串，表示一次询问。

输出格式

按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

输入输出样例

输入 #1

输出 #1

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤T,n,q≤10^5，且输入字符串的总长度不超过3× 10^6。输入的字符串只含大小写字母和数字，且不含空串。

说明

std 的 IO 使用的是关闭同步后的 cin/cout，本题不卡常。

---

#include 
#include 
#include 
#include 
using namespace std;
int cnt[3000005],trie[3000005][65]; 
//一维数组cnt[N]用于存字符出现的次数
//二维数组用于连接字典树的各个节点
//二维数组的第二个位置需存‘A’~‘Z’,‘a’~‘z’,‘0’~‘9’共62个位点
int T,idx，n,q;
char s[3000005];
 
int getnum(char x) //用于将字符转换成存入位置的序号
{
	if('A'<=x&&x<='Z') return x-'A';
	else if('a'<=x &&x<='z')
	return x-'a'+26; //‘a’~‘z’存在‘A’~‘Z’往后的位置
	else  return x-'0'+52;
}
 
void maketree(char s[])
{
	int p=0,len=strlen(s); //p用于统计当前字符在树中的序号
	for(int i=0;i
	{
		int number=getnum(s[i]);
		if(trie[p][number]==0) 
		trie[p][number]=++idx;
		p=trie[p][number];
		cnt[p]++;	
	}
}
 
int search(char s[])
{
	int p=0,len=strlen(s);
	for(int i=0;i
	{
		int number=getnum(s[i]);
		if(trie[p][number]==0) return 0;
		p=trie[p][number];
	}
	return cnt[p];	
}
 
int main()
{
	scanf("%d",&T);
	for(int k=1;k<=T;++k)
	{
		for(int i=0;i<=idx;++i)
			for(int j=0;j<=122;++j)	
			trie[i][j]=0;
		for(int i=0;i<=idx;++i)
		cnt[i]=0;
		idx=0;	
		//每次循环都是重新建字典树的过程，因此数组及指针需要清零	
		cin>>n>>q;
		for(int i=1;i<=n;++i) //输入字符串构建字典树
		{
			scanf("%s",s);
			maketree(s);
		}
			
		for(int i=1;i<=q;++i) //在字典树中查找字符串
		{
			scanf("%s",s);
			printf("%d\n",search(s));	
		}
	}
	return 0;
}

---

相关练习题：

（待补充）1.洛谷 P1628 合并序列

 个人一开始的思路就是字典树，但是太菜了最后的查找与输出肝不出来QAQ 

 

 

---

个人觉得讲得很好的课