2006 年全国信息学冬令营讲座
Trie 图的构建、活用与改进
Maigo 2006.1.14
我们知道 trie 树（也叫字母树）这种数据结构。它是词典的一种存储方式。词典中的
每一个单词在 trie 树中表现为一条从根结点出发的路径，路径中边上的字母连起来就形成
对应的单词。图 1 就是一棵 trie 树，其中含有 a,abc,bac,bbc,ca 五个单词。
利用 trie 树可以对词典中的单词进行一些适合用树这种数据结构进行的操作，如求两
个单词的公共前缀长度（在树中表现为求两个单词对应结点的最近公共祖先）。其实，如
果把 trie 树加以改造，多连一些边，形成的 trie 图在解决多模式串匹配问题上会发挥奇效。
左：图 1，一棵含有五个
单词的 trie 树。红色表示单词
终止的位置。
右 ： 图 2 ，由 图 1 的 trie
树改造成的 trie 图。红色表示
危险结点，白色表示真安全结
点，蓝色表示新加的边。为简单起见，危险结点以下的结点及与之关联的边没有画出。
一、Trie 图的构建
我们通过一个例题来探究 trie 图的构建方法。
【例 1】不良单词探测器
【题目描述】给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文
本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若 rob
是不良单词，那么文本 problem 含有不良单词。
【输入】第一行为一个整数 n，表示不良单词的个数。接下来 n 行是词典。下面一行为一
个整数 m，表示文本的行数。接下来 m 行是文本。
【输出】如果文本包含不良单词，输出一行“Yes”，否则输出一行“No”。
【样例输入】
1
rob
1
internetproblemsolvingcontest
【样例输出】
Yes
【备注】因本题只是用来讨论 trie 图的构建方法，故未给出数据范围。
【分析】判断文本是否包含不良单词可以一行一行地判断。而判断长为 L 的一行文本 s 是
否含有不良单词可以这样进行：让 i 从 1 变化到 L，依次判断 s 的前 i 个字符构成的字符串
是否以不良单词结尾。
然而，我们希望在判断 s 的前 k 个字符时，能够利用前 k-1 个字符的结果，即这两个状
态间可以方便地进行转移。注意到 trie 树中的边正如一个个“方向标”，因此我们有了一个美
xwc111
- 粉丝: 0
- 资源: 9
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0