- 浏览: 498562 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
Tire树:
先简单解释一下Trie。“Trie”这个单词来自于"retrieve",可见它的用途主要是字符串查询。Trie不发tree的音,而发try的音。
应用
题目大意:
统计子串出现的次数,规定子串的长度不超过8.
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1302
trie算法的思路大概如下:
对输入的长串S 想将所有长度位1-8的子串存入trie树,并在子串末节点上记录下字串出现的次数,然后针对每个输入的查询串s 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。
仍段代码先:
这个题目也可以用hash做.
基本思路:
这里采用的最简单的26进制的函数对子串进行hash,由于26^8 会超出int的范围所以在计算hash值时需要64位的整数。在算出每个子串的 hash值后就将相应的slot标记好,并记录下这个slot被标记过几次,然后对各查询子串也用相同的hash函数来处理,然后查询子串所在的slot 的计数器就行了。
先简单解释一下Trie。“Trie”这个单词来自于"retrieve",可见它的用途主要是字符串查询。Trie不发tree的音,而发try的音。
应用
题目大意:
统计子串出现的次数,规定子串的长度不超过8.
http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1302
trie算法的思路大概如下:
对输入的长串S 想将所有长度位1-8的子串存入trie树,并在子串末节点上记录下字串出现的次数,然后针对每个输入的查询串s 只要在这颗树上查找 一遍就能找到得到该子串出现的次数。
仍段代码先:
#include <iostream> using namespace std ; class trie { private : int count[26] ; trie * child[26] ; public : trie () { int i ; for ( i = 0 ; i < 26 ; i++ ) { count[i] = 0 ; child[i] = NULL ; } } ~trie () { int i ; for ( i = 0 ; i < 26 ; i++ ) { delete child[i] ; } } void insert ( const char *key , const int & leng ) //生成了字典树,这次操作统计的次数全部以*key开头 { if ( leng == 0 ) return ; int index = *key - 'a' ; if ( child[index] == NULL ) child[index] = new trie ; count[index]++ ; child[index] -> insert ( key + 1 , leng - 1 ) ; } int quary ( const char *key ) //返回子串出现的次数 { if ( * ( key + 1 ) == '\0' ) //最后一个字符 return count[*key - 'a'] ; if ( child[*key - 'a'] == NULL ) //只有遇到不存在的部分子串,必定返回0. return 0 ; return child[*key - 'a'] ->quary ( key + 1 ) ; //递归寻找下一个字符 } } ; char s[32768 + 10] ; int main () { int stringLength , quaryNumber , left , right , substringLength , test = 1 ;; while ( scanf ( "%s" , s ) != EOF ) { trie stringTrie ; substringLength = 8 ; stringLength = strlen ( s ) ; for ( left = 0 ; left + substringLength <= stringLength ; left++ ) stringTrie.insert ( s + left , substringLength ) ; //生成了字典树 for ( substringLength = 7 ; left < stringLength ; left ++ , substringLength-- ) stringTrie.insert ( s + left , substringLength ) ; //添加最后7个开头子串的统计数 scanf ( "%d" , &quaryNumber ) ; printf ( "Case %d:\n" , test++ ) ; while ( quaryNumber -- ) { scanf ( "%s" , s ) ; printf ( "%d\n" , stringTrie.quary ( s ) ) ; } } return 0 ; }
这个题目也可以用hash做.
基本思路:
这里采用的最简单的26进制的函数对子串进行hash,由于26^8 会超出int的范围所以在计算hash值时需要64位的整数。在算出每个子串的 hash值后就将相应的slot标记好,并记录下这个slot被标记过几次,然后对各查询子串也用相同的hash函数来处理,然后查询子串所在的slot 的计数器就行了。
#include<iostream> using namespace std ; typedef long long __int64 ; char s[1<<16] ; const int HASH_SIZE = 1<<18 ; __int64 mark[HASH_SIZE] ; int counter[HASH_SIZE] ; int getHashVal ( __int64 tmp ) { return tmp&(HASH_SIZE-1) ; } void insert ( __int64 tmp ) { int val = getHashVal ( tmp ) ; int index = val ; //index代表下标和tmp的值不是对应的,因此每次都需要需要tmp对应的index. while ( mark[index] != -1 && mark[index] != tmp ) { index++ ; if ( index == HASH_SIZE ) index = 0 ; } counter[index]++ ; mark[index] = tmp ; } int query ( __int64 tmp ) { int val = getHashVal ( tmp ) ; int index = val ; while ( mark[index] != -1 && mark[index] != tmp ) { index++ ; if ( index == HASH_SIZE ) index = 0 ; } return counter[index] ; } int main() { __int64 tmp ; int t , Q ; for ( t = 1 ; scanf ( "%s" , s ) != EOF ; ++t ) { memset ( mark , -1 , sizeof ( mark ) ) ; memset ( counter , 0 , sizeof ( counter ) ) ; printf ( "Case %d:\n" , t ) ; for ( int i = 0 ; s[i] != '\0' ; ++i ) //s[i] != '\0',因此所有的子串都可以遍历到. { tmp = 0 ; for ( int k = 0 ; k < 8 && s[i + k] != '\0'; ++k ) //转化为27进制的一个数 { tmp = tmp * 27 + s[i + k] - 'a' + 1 ; insert ( tmp ) ; } } scanf ( "%d" , &Q ) ; while ( Q-- ) { scanf ( "%s" , s ) ; tmp = 0 ; for ( int i = 0 ; s[i] != '\0' ; ++i ) { tmp = tmp * 27 + s[i] - 'a' + 1 ; } printf ( "%d\n" , query ( tmp ) ) ; } } return 0; }
发表评论
-
为什么堆排比快排慢
2010-12-16 15:25 2981[节选]http://mindhacks.cn/200 ... -
使用map和hash_map的效率问题
2010-12-09 19:49 68551,选择map容器,是为了更快的从关键字查找到相关的对象。 与 ... -
斐波那契堆
2010-07-04 11:37 181, http://kmplayer.iteye.com/ad ... -
斐波那契堆
2010-07-04 11:36 1390学习的地方: http://en.wikipedia.org/ ... -
Sunday算法
2010-07-02 11:38 89171,Sunday算法是Daniel M.Sunday于1990 ... -
BM算法.
2010-07-02 10:53 76251,BM算法是Boyer-Moore算法的简称,由Boyer ... -
优先级队列
2010-06-17 23:15 11601,优先级队列是不同于 ... -
计数排序
2010-05-04 16:59 7491,计数排序是一个非基于比较的线性时间排序算法。 它对输入的数 ... -
归并排序
2010-05-04 16:47 8781,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采 ... -
求大数阶层
2010-05-04 16:40 13191,思想类似于大数的加减乘法. 数组的每个元素维护一个4位数. ... -
基数排序
2010-05-03 16:45 865详细解释参考:http://en.wikipedia.org/ ... -
求两个数组的中位数
2010-05-02 12:08 40691,题目 有两个数组,均已经按升序排列好,编程序计算这两个数组 ... -
imba的bit向量
2010-04-22 17:30 8961,先给出一个模板. #include <iostr ... -
编写自己的malloc
2010-04-19 17:03 14791,如果一个程序大量调用malloc,程序的很多时间将会消耗在 ... -
快速排序
2010-04-01 13:50 7081,给出一个实现实例. #include <iost ... -
md5算法
2010-03-31 10:35 2638Message Digest Algorithm MD5( ... -
堆排序
2010-03-23 10:48 8681,"堆"定义 n个关 ... -
改进的线性筛法_寻找素数
2010-03-03 10:41 15731,实例代码: #include <iostream ... -
求有向图的强连通分量(scc):Tarjan算法
2010-02-28 15:41 142411,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强 ... -
最近公共祖先LCA:Tarjan算法
2010-02-28 15:25 177991,并查集+dfs 对整个树进行深度优先遍历,并在遍历的过程中 ...
相关推荐
关于tire树一些简单的使用和应用
(2) 树有s个外部结点 (3) 树的高度等于X中最长串的长度 (4) 树中的结点数为O(n) (1) 在root结点中查找第('b'-'a'=1)号孩子指针,
NULL 博文链接:https://ansjsun.iteye.com/blog/441658
NULL 博文链接:https://tanghongjun1985.iteye.com/blog/548759
后缀tire树(tire图),用于多字符串匹配。
Tire 字典树 方面的论文
数据结构指的是“一组数据的存储...数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
利用Tire树实现一个音域单词辅助记忆系统,完成相应的建表和查表程序。 程序主要实现对单词的插入、删除和查找。其中查找部分又分精确查找和模糊查找。 利用文件对单词进行保存和读取操作以增强程序的可用行性。
DoubleArrayTrie 双端trie树的python实现 ...其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
里面基本包含了全文检索引擎的所有技术,包括词典分词,索引,检索等,其中词典分词采用的是基于双数组tire树的最大匹配法,索引部分参考了lucene的部分实现,检索部分应用了布尔检索和向量模型的排名算法,基本可以...
包括 插入 删除 是否包含 自动补全 两棵tire树的合并 自动纠错
ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了
红黑树、AVL树、Hash树、Tire树、B树、B+树。 图算法(比较少,也就两个最短路径算法理解吧) 计算机网络 OSI7层模型(TCP4层)等 数据库 数据库(最多的还是mysql,Nosql有redis) 索引(包括分类及优化方式,失效...
Tire树的基本实现和特性 并查集的基本实现和特性 剪枝的实现和特性 双向BFS的实现和特性 启发式搜索的实现和特性 AVL树和红黑树的实现和特性 位运算基础与实战要点 布隆过滤器的实现及应用 LRU Cache的实现及应用 ...
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
嵌入式系统中基于trie树的拼音输入法的实现,李巧红,,介绍一种中文拼音输入法的实现方式,着重讨论了字库的设计及基于Trie树检索方法的实现。Trie树是基于关键码空间分解的树结构,其内�
这道题是DFS+前缀树,是一道标准的模板题 这里面的Tire类的定义写的方法与之前的 208 略有不同,但基本上一样。只是单独定义了一下TireNode节点类。 //定义节点,类/结构体 class TireNode { public: TireNode()...
ACM国家集训队2006论文集(动态树、动态规划、tire图、最短路算法、棋盘分割)
《数据结构》)字典树课程设计《英语字典的维护与识别》的代码实现。。。。。