Trie树 （字典树）

什么是字典树？

一种高效的存储和查找字符串集合的数据结构
存储的字符串的个数不会太多

可以插入，查询，每次存入一组字符串结尾要进行着标记

模拟Trie树

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;
//因为最多就有26个英语字母，所以最多就是26个分支

char str[N];

//插入字符串
void insert(char str[])
{
	int p = 0;//从根节点出发
	for (int i = 0; str[i]; i ++)
	{
		int u = str[i] - 'a';//确定这个字符的位置
		if (!son[p][u])//如果没有在字典树中插入这个字符，就给这个字典树上加上当前这个字符的分支
			son[p][u] = ++ idx;//idx是表示当前节点下的索引

		p = son[p][u];//进入到下一个字符，进行如上的操作处理插入字符串
	}
	cnt[p] ++;//完成插入后再给插入字符串的末尾标记一下，也就是计数，方便后续在其中直接查询字典树中一些字符串的出现个数
}


//查询

int query(char str[])
{
	int p = 0;
	for (int i = 0; str[i]; i ++)
	{
		int u = str[i] - 'a';
		if (!str[i])//如果出现了一个字符不能再当前所在的层次当中，不能够找到其所对应的分支，那么就直接退出查询函数。
			return 0;
		p = son[p][u];//依次到下一个层次，直到查询字符串到了结尾或者不能找到返回函数。
	}

	return cnt[p];//返回查询字符串当中末尾处的计数标记，即是对应查询字符串的出现次数。
}

int main()
{
	int n;
	cin >> n;
	while (n --)
	{
		char op[2];

		cin >> op >> str;
		if (op[0] == 'I')
			insert(str);
		else
			cout << query(str) << endl;
	} 

	return 0;

}

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

293370 0元 限免

英特尔 OpenCV 初级认证课程

7890 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

42078 0元 限免