了解这个数据结构之前我们需要了解它能被用来做什么
字典树又称单词查找树,Tire树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
说到底,字典树就是用来查询公共前缀的一个工具,延伸的话可以用来进行串匹配,词频统计等,也是学AC自动机
的前置技能. 所谓的字典树,其实就是一个n叉树
我们对于每个字母,如果有公共前缀的,我们找到它的前缀,在后面不同的部分建立不同的子节点,比如说apple
,appear
,appxy
三个不同的单词,公共前缀为app
,所以建树如下: 如果下面有一个单词为
apzl
的话,建树如下 也就是只注意前缀相同的部分,后面即使有一样的字母也重新建立子节点
那么问题来了,单词的第一个字母不止A
啊,应该怎么办? 其实不难,学过二分图的应该能想出来:设置一个超级源点,我们在第一个字母上面再设一个超级源点,这样计算的时候不考虑他就行了,这样第一层就可以和下面的子节点一样建立了 如图所示(ps:此图有误,apply
应该为appxy
)
又是喜(sang)闻(xin)乐(bing)见(kuang)的代码环节了 个人由于ACM的原因,就只放数组实现的板子了,(反正懂原理了指针版的也挺简单的) 由于数组不能动态开内存,所以我们就得采用模拟的形式了,这里其实用了一点并查集的思想,各位客官看下图 由于不能动态分配内存,同时字典树又是比较耗费空间的,所以我们的内存分配尽可能大,开一个二维数组
tire[maxn][26]
,然后tire[i][j] = k 代表编号为i
的节点的第j
个孩子是编号为k
的节点,这里的j
通常指当前位的字母A-Z
然后关于编号,我们这里的存树方式是:如果要生成新节点,则编号++,否则编号不动,所以如上图,APPLY
的对应编号应该为1,2,3,4,10,11
; 同时有:
tire[1]['A'-'A'] = 2;
tire[2]['P'-'A'] = 3;
tire[3]['P'-'A'] = 10;
tire[10]['X'-'A'] = 11;
tire[11]['Y'-'A'] = 0;
这样,查找的时候利用并查集的思想不断向下查找即可 代码如下
1 | /*头文件可以忽略,只是一些常用的宏*/ |