Trie 字典树（前缀树）_前缀树 磁盘存储

Trie 或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

描述：向 Trie 中插入一个单词 word

实现：首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点标记一下，表示它是一个单词的末尾。

总结
通过以上介绍和代码实现我们可以总结出 Trie 的几点性质：

Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。

 Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

最后，关于 Trie 的应用场景，希望你能记住 8 个字：一次建树，多次查询。(慢慢领悟叭~~)

 

 五角星标记的是每个插入字符串的最后一个字母，用cnt[p]++标记；然后判断一个字符串T有多少个前缀，只需要顺着树走一遍，遇到几个五角星就说明有多少个字符串是T的前缀。

#include<iostream>
#include<string>
using namespace std;
string str;
const int N=1e5+5;
int n,m;
int son[N][26];
int ind;
int cnt[N];
void ins()
{
	int p=0;
	for(int i=0;i<str.size();i++)
	{
		int &s=son[p][str[i]-'a'];// &s这种写法，可以在s=++ind后，son[p][str[i]-'a']也随之变化,更加省事。
		if(!s)s=++ind;//trie上没有对应的字符，就开辟新的
		p=s;
	}
	cnt[p]++;//每个字符串最后一个字母标记一下
 } 
 int query()
 {
 	int res=0,p=0;
 	for(int i=0;str[i];i++)
 	{
 		int &s=son[p][str[i]-'a'];
 		if(!s)break;//trie上没有对应的字符，就结束，因为再往下也没有对应的前缀了
 		p=s;
 		res+=cnt[p];
	 }
	 return res;
 }
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>str;
		ins();
	}	
	for(int i=0;i<m;i++)
	{
		cin>>str;
		cout<<query()<<endl;
	}
	return 0;
 } 

注释：代码中的p意思是节点编号，root的编号是0，往下每一个节点的编号都不一样(1,2,3,.......)。