大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
字典树又称单词查找树,Trie树,是一种树形结构。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。
之前在网上找的都是些用指针实现的,代码看起来很难懂,今天学习了一种用数组实现的。学习起来简单易懂
int ch[200010][27]; //节点编号
int sz; //字典树节点个数
int val[200010]; //节点的值
void init()
{
sz=1;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
void insert(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
ch[u][c]=sz++;
u=ch[u][c];
val[u]++; //!!!
}
}
int query(char *s)
{
int u=0,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'a';
if(!ch[u][c])
return 0;
u=ch[u][c];
}
return val[u];
}
说明一下代码中注释的部分,这个语句放在for循环外面有时也是很方便的,当遇到一些特殊的标记,比如1或-1,就代表着字符串的结束,而字符串的中间部分默认都为0。这在有些题中使用是很方便的。
这个数组实现和指针的版本也是有些区别的,数组的版本并不怎么直观,因为在数组中实现的树没有“层”的概念。代替的是节点的“编号”,通过这个编号可以向“下一层”去找节点,也可以通过编号获得字符串的一些其他信息,很多题都需要在结构体或是数组中记录或保存信息,当然这个下标利用的就是“编号”。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/197523.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...