什么是字典树
基本概念
字典树,又称为单词查找树或Tire树,是一种树形结构,它是一种哈希树的变种,用于存储字符串及其相关信息。
基本性质
运用方面
典型应用是用于统计,排序和保存大量的字符串(不仅限于字符串),经常被搜索引擎系统用于文本词频统计。
优点缺点
字典树是经典的空间换时间的数据结构,利用字符串的公共前缀来减少查询时间,最大限度的减少无谓的字符串比较,查询效率据说比哈希树高。
但缺点就很显然了,就是空间比较大……
举个栗子
什么不太了解,没事,让我们来结合栗子来分析一下!
我们首先读入四个字符串
在没有读入前,我们有一个空空的根节点;
接着我们插入单词ba;
接着插入单词b,由于根节点有连向b的子节点,所以只需路径上的s++就好了;
接着插入单词bank,ba之前就有,只需s++,而nk需要在ba后添加子节点完成存储;
最后插入单词abc;
如何构造字典树
我们来结合程序一步一步来构造这棵可爱的字典树吧!!
构造节点
我们需要运用struct来存储字典树上每个节点的信息:
struct node
{
int s,v[27],val;
node()
{
s=0;
memset(v,-1,sizeof(v));
}
}t[410000];
s是用来存储有多少个单词进过了这个节点,v是用来存储这个点从a到z的儿子节点分别在哪,而val则是存储这个节点的权值,至于权值代表什么,就要依照题目灵活变换了。
构造字典树
我们先抛出程序:
int bt(int root)
{
int len=strlen(a+1);int x=root;
for(int i=1;i<=len;i++)
{
int y=a[i]-'a'+1;//将a^z转化为1^26
if(t[x].v[y]==-1)t[x].v[y]=++tot;
x=t[x].v[y];t[x].s++;
}
}
首先我们先读入了一个字符串a,它的长度为len;
接着我们对于它的字符进行循环处理,当我们处理到这个字符串的第i个字符的时候,我们要进行分类讨论——
这样一棵完整的字典树就出来了!
模板&&模板题
就是一道裸题,查询时输出对应节点的s就好了;
附上代码:
#include<bits/stdc++.h>
using namespace std;
struct node
{
int s,v[27];
node()
{
s=0;
memset(v,-1,sizeof(v));
}
}t[410000];
char a[410000];
int i,j,k,m,n,tot,js,jl;
int bt(int root)
{
int len=strlen(a+1);int x=root;
for(int i=1;i<=len;i++)
{
int y=a[i]-'a'+1;
if(t[x].v[y]==-1)t[x].v[y]=++tot;
x=t[x].v[y];t[x].s++;
}
}
int solve(int root)
{
int len=strlen(a+1);int x=root;
for(int i=1;i<=len;i++)
{
int y=a[i]-'a'+1;
if(t[x].v[y]==-1)return 0;
x=t[x].v[y];
}
return(t[x].s);
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",a+1);
bt(0);
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",a+1);
printf("%d\n",solve(0));
}
}
结语
通过这篇BLOG相信你已经掌握了Trie树,那就向着AC自动机前进吧!希望你喜欢这篇BLOG!