文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 字典树模板及解析
侵权投诉

字典树模板及解析

字典树模板及解析

字典树模板

trie的原理是利用字符串集合中字符串的公共前缀来降低时间开销以达到提高效率的目的。

它具有以下性质:1,根结点不包含任何字符信息;2,如果字符的种数为n,则每个结点的出度为n(这样必然会导致浪费很多空间,这也是trie的缺点,我还没有想到好点的办法避免);3,查找,插入复杂度为O(n),n为字符串长度。

举一个例子,给50000个由小写字母构成的长度不超过10的单词,然后问某个公共前缀是否出现过。如果我们直接从字符串集中从头往后搜,看给定的字符串是否为字符串集中某个字符串的前缀,那样复杂度为O(50000^2),这样显然会TLE。又或是我们对于字符串集中的每个字符串,我们用MAP存下它所有的前缀。然后询问时可以直接给出结果。这样复杂度为O(50000*len),最坏情况下len为字符串最长字符串的长度。而且这没有算建立MAP存储的时间,也没有算用MAP查询的时间,实际效率会更低。但如果我们用trie的话,当查询如字符串abcd是否为某字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。实际查询复杂度只有O(len),建立trie的复杂度为O(50000).这是完全可以接受的。

如给定字符串集合abcd,abd,cdd,efg,hij,hi六个字符串建立的trie tree如下图所示:

字典树模板及解析

查找一个字符串时,我们只需从根结点按字符串中字符出现顺序依次往下走。如果到最后字符串结束时,对应的结点标记为红色,则该字符串存在;否则不存在。

插入时也只需从根结点往下遍历,碰到已存在的字符结点就往下遍历,否则,建立新结点;最后标记最后一个字符的结点为红色即可。 同时我们看到,如果字符的种类为n,则需要结点的个数为n级数。(谁有好办法降低空间开销,请告诉我)

题目:doc.guandang.net 题目和我上面举的例子差不多,是说给定一个字符串集合,然后每次询问时给出一个字符串,问以该字符串为前缀的字符串在集合中有多少个。先给个用MAP版本的,限时2000MS的题目,用MAP,1750MS,险过。

#include<iostream>

第1页

热门文档

相关文档

  • 字典树模板

    字典树模板 格言:编码并不难,难就难在一道题该用啥算法啊 格言:编码并不难... 应届生求职季宝典 英文个人简历模板 创意简历模板汇集 推理型题分析与总结...

  • 字典树模板acm竞赛可用

    字典树模板及解析 18页 2财富值 ACM常用模板 字典序全排列 1页 免费 ACM... 字典树模板acm竞赛可用 隐藏>> 分享到: X 分享到: 使用一键分享,轻松...

  • 应用字典树的题目

    字典树模板及解析 18页 1下载券 字典树理论 7页 2下载券 喜欢此文档的还...题目:单词(词组)检索 现在有一个英文字典(每个单词都是由小写的'a'-'z'组成...

  • 字典树理论

    字典树 trie 树把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后... 字典树知识 3页 1下载券 字典树模板及解析 18页 1下载券 喜欢此文档的还...

  • 字典树模板acm竞赛可用

    字典树模板及解析 18页 2财富值 ACM_算法模板 79页 1财富值搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库投诉中心;如要提出...

  • 根据文本构造字典树能检索

    字典树 16页 1下载券 字典树1 7页 2下载券 字典树及应用 7页 1下载券 字典树模板 6页 1下载券 应用字典树的题目 5页 免费喜欢此文档的还喜欢...

  • Trie树&字典树的简介及实现

    字典树的简介及实现 Trie 树字典树的简介及实现 1 综述 又称单词查找树,... 2013年注会经济法统考真题 2013年注会设计统考真题及答案160份文档 ...

  • 字典树

    这里给出生成字典树和查找的模版: 生成字典树: void createTrie(char *str) {... 2014教师资格材料分析辅... 2014小学教师资格考试《... 2014年幼儿园教师资格...

  • 蓝杰贾彪字典压缩算法详解

    字典树模板及解析 18页 1下载券 _词典学_解析 7页 1下载券 VBA字典用法...数据压缩的简史 数据压缩的分类 字典压缩的基本原理 与哈夫曼算法的比较 ? ? ...

  • 用户数据字典模版

    上海烟草机械有限责任公司_信息技术部 用户数据字典 XXX 系统 用户数据字典 文件... 字典树模版 3页 免费 客户综合信息数据字典 3页 免费 用户如何有效地利用数据...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email