Trie

⬅ 返回

1、定义

Trie是高效的存储和查找字符串集合的数据结构

2、例题

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x。
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

3、思路

Trie树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，就创建一个结点。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2;如果son[1][0] = 0，则意味着没有值为a子结点。

通常定义为son[p][u]

p表示当前结点号 根节点root的结点号为0

u表示的是26个字母

son[p][u]存储的即是结点p的u字母分支对应的结点号

最后用num[p]记录终点为结点p的字符串个数

3、代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int son[N][26];
int num[N];
int idx=1;//结点号
 
int main(){
	int n;
	cin>>n;
	while(n--)
	{
		char c;
		cin>>c;
		string s;
		cin>>s;
		------------------------------------------------------------
		if(c=='I')
		{
			int p=0;//p指向root结点
			for(int i=0;i<s.length();i++)//遍历字符串
			{
				int u = s[i]-'a';
				if(son[p][u]==0)//如果没有该子节点就创建一个，结点号为idx
					son[p][u]=idx++;
				p=son[p][u];//能p指向该子结点
			}
			num[p]++;//终点为p结点的计数加一
			
		}
		else if(c=='Q')
		{
			int p=0;
			for(int i=0;i<s.length();i++)
			{
				int u = s[i]-'a';
				if(son[p][u]==0)
					son[p][u]=idx++;
				p=son[p][u];
			}
			cout<<num[p]<<endl;//同上
			
			-------------------------------------------------------------------------------
		}
	}
	
	
}