你人没了
你人没了
全部文章
分类
acm(47)
fft(1)
博弈(1)
心绪(2)
日记(1)
未归档(54)
树状数组(2)
鸟哥的私房菜(服务器篇)(2)
归档
标签
去牛客网
登录
/
注册
你人没了的博客
全部文章
(共110篇)
DC3算法模板学习笔记
今天看了一下洛谷sx视频,后缀数组双关键字排序瞬间秒懂,昨天刚了一下午没有看懂的后缀数组基数排序代码有了一点点突破。 对第二关键字桶排序,保持相对顺序不变,则个位数字有序,对第一关键字桶排序,由于第一关键字相同情况下个位总是递增或持平,所以保持有序。 ——《高级数据结构》 #i...
2019-05-04
0
288
DC3算法初步学习笔记
——《高级数据结构》 “linear work suffix array construction”的文章中提出了后缀数组的线性时间构造算法。其中DC3算法的时间复杂度和空间复杂度均为O(n);其中DC3(Difference Covor modulo3)算法的时 间复杂度仍为O(n);更是一般化的...
2019-05-03
0
1156
后缀数组的定义
——《高级数据结构》 1.区间 闭区间[i,j]={i,…,j},开区间[i,j)=[i…j-1] 2.字符串 待构建后缀数组的字符串用T来表示。T的长度为n,下标范围为0到n-1。字符串中第i个字符用ti表示,所以T[0,n)=t0t1…tn-1。在C语言中,字符串数组末尾以特殊字符‘\0’结尾(...
2019-05-03
0
335
后缀数组初步
——《高级数据结构》 1991年,首次提出了后缀数组(suffix array)的概念。当时,这篇文章是为了提出一种新的数据结构,从而在处理"在线字符串查询"任务中相比较后缀树而言,能够更节省空间(只需要后缀树的1/5-1/3空间)。可见,后缀数组主要是作为后缀树的一个精简的替代...
2019-05-02
0
344
后缀树的应用
——————《高级数据结构》 在这一节中,我们将给出几个常见的后缀树的应用,并且你将会看到它与其他处理字符串的算法与数据结构(例如KMP算法,AC自动机等)之间的比较。后缀树是一个非常强大的处理字符串问题的工具,并且企图在这一节短篇幅里面穷尽其应用是不可能的。因此,这里的介绍旨在抛砖引玉,更...
2019-05-01
0
495
后缀树的相关证明
——《高级数据结构》 1.后缀树中的节点个数至多为2m-1,其中m为字符串的长度。 证明:由后缀树的定义我们知道一共有m个叶节点,并且每个内部节点至少有2个孩子节点。假设总共有n个节点,则内部节点的个数为n-m。于是,我们可以得到如下的不等式:2(n-m)+1<=n;即n<=2m-1。因...
2019-05-01
0
495
块状链表继续笔记
——《高级数据结构》 操作1: 合并Merge(curBlock,nextBlock) 该操作的目的是将相邻两个块合并。一般当相邻两个块的大小加起来不超过n的1/2的时候需要进行合并操作。这一步将nextBlock合并给curBlock,其伪代码如下: function Merge(curBlo...
2019-05-01
0
492
块状链表与块状树初步
1.块状链表的基本思想 常见的线性表结构修改操作有:再某一位置后插入一段数,从某一位置开始删除连续若干个数,我们不妨先来看看数组和链表这两种常用线性结构的实现效果。 可见,它们各有各的优势和缺点,且恰巧是优势互补。我们不禁想,如果把两者结合起来,是不是会有更优异的表现?块状链表正好是基于这个思想,将...
2019-05-01
0
698
SuffixTree
早上照着书本敲了一个小时 崩掉了,先扔这里,以后再调试 #include<cstdio> #include<cstring> #include<vector> #include<list> using namespace std; //后缀树节点预...
2019-05-01
0
417
鸟哥的私房菜第1章
摸索了两节晚课,终于试着把virtualbox和centos的镜像iso文件下载好并且能够安装上了,百度了一波,感觉和书上所说的并不一致, 1.书上说(以centos6.0为例,由于是用光驱开机来安装系统,因此要进入BIOS,选择光驱开机,兵器而降centos6.x的dvd放入光驱中)然后我并...
2019-04-30
0
351
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页