• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

trie树

开发技术 开发技术 3周前 (09-07) 23次浏览

trie 树,又叫字典树,前缀树,可以用来求查询这个字符串的数量,或者以这个字符串为前缀的字符串的数量。

trie 树用了一个前缀的思想,就是把每个字符串拆一位位拆开来,然后存在树的边上,比如有 cup,apple,cake,app,blog 这几个单词,那么我们就可以构建这样一棵有根树:
trie树
但是,在树上边是很不好维护的,于是我们可以把他放在这条边的两个端点中,深度较大的那个点上,像这样:
trie树
但这样还没完,我们如何判断这是一个完整字符串呢?比如,你如何知道 ca 是不是一个完整的字符串呢?是判断最后一个字符是否为叶子节点吗?明显不是,上面的例子中,app的最后一个字符就不是叶子节点。那怎么办呢?直接给节点打个标记嘛~
于是,我们知道了什么是 trie 树,接下来我们要解决插入和查询的问题。
我们可以开一个数组,用 (trie_{i,j}) 表示节点 i 的儿子中,是字符 j 的节点的编号。当然,我们不能用字符做下标,但是我们可以把他转成数字,比如题目说明只会出现 a~z 的字符,那么我们可以用 x-'a' 来表示字符 x。
然后,对于插入和查询操作,我们只要枚举字符串的每一位,然后用一个变量 rt 来记录当前节点的编号。然后,对于第 i 个字符,我们只要查询它是否存在,也就是 (trie_{rt,s[i-1]}) 是否为 (0)(字符串下标从 (0) 开始),如果为 (0),若是插入,则加入这个节点;若是查询,则返回 false。
代码如下:

void insert(string s)
{
	int len=s.length(),root=0;//root即上面的rt
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) trie[root][id]=++tot;//tot记录节点数
		root=trie[root][id];
	}
	v[root]=true;//v就是用来记录是否为字符串结尾的、
	return ;
}
bool find(string s)
{
	int len=s.length(),root=0;
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) return false;
		root=trie[root][id];
	}
	if(v[root]) return true;
        else return false;
}

然后,上面说到我们可以查询以这个字符串为前缀的字符串有多少,怎么弄呢?我们可以用 (sum_i) 表示有从根节点到 (i) 这个字符串(trie 树上从根节点到一个节点的路径其实就是一个字符串的前缀)前缀的字符串的数量(有点绕、),然后每次插入走到一个节点就 sum[i]++ 即可,而查询则和上面的一样,最后返回末尾节点的 sum 即可。
代码实现如下:

int fin_pre(string s)
{
	int len=s.length(),root=0;
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) return 0;
		root=trie[root][id];
	}
	return sum[root];
}

整体代码实现如下:

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int n,m;
int tot,trie[1000005][26],sum[1000005];
bool v[1000005];
void insert(string s)
{
	int len=s.length(),root=0;
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) trie[root][id]=++tot;
		root=trie[root][id];
		sum[root]++;
	}
	v[root]=true;
	return ;
}
bool find(string s)
{
	int len=s.length(),root=0;
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) return false;
		root=trie[root][id];
	}
	if(v[root]) return true;
	else return false;
}
int find_pre(string s)
{
	int len=s.length(),root=0;
	for(int i=0;i<len;i++)
	{
		int id=s[i]-'a';
		if(trie[root][id]==0) return 0;
		root=trie[root][id];
	}
	return sum[root];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	for(int i=1;i<=m;i++)
	{
		int opt;
		scanf("%d",&opt);//opt=1表示查询这个字符串是否存在,opt=2表示查询包含这个字符串前缀的字符串的数量
		string s;
		cin>>s;
		if(opt==1) printf("%sn",find(s)?"Yes":"No");
		else printf("%dn",find_pre(s));
	}
	return 0;
}

由于没有找到合适的模板题所以无法测验,但 insert 和 find 函数是没问题的,find_pre 也不会出太大的问题


程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2020/09/trie%e6%a0%91/
喜欢 (1)