Mai Icy

“2024 年 4 月”

ACM程序课算法笔记14——KMP算法

ACM程序课算法笔记14——KMP算法 简介 KMP算法是一个查找子串的算法,这种算法感觉在题目中都几乎不会出现了,但我们应当注意的是它的思想,算法思想大于算法本身。 问题 KMP算法输入两个字...

算法学习笔记10——康托展开

算法学习笔记(10): 康托展开 可以求一个组合的全排列的名次 比如:对于序列1,2,3 则序列排名为 1 2 3;1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1 这个排...

ACM程序课算法笔记13——线段树入门

ACM程序课算法笔记13——线段树入门 线段树介绍 线段树的功能是维护一个数组,当然你可以用普通数组维护,线段树只是一种维护方式,它的特点是可以在O(LogN)的时间复杂度完成单点修改,区间修改...

ACM程序课算法笔记12——树状数组

ACM程序课算法笔记12——树状数组 引入 对于数据储存,我们通常有求区间的需求,因此产生了不同的用于储存数据的数据结构,例如求区间和问题,我们会使用的前缀和数组。 本次我们考虑的问题是:单点更...

算法学习笔记9——后缀数组

算法学习笔记(9): 后缀数组 定义 后缀数组是对后缀的一个排序,每个后缀按照字典序进行排序,然后用两个数组来映射它们自己和它们的排名。 同时,为了便于记录后缀,我们记字符串s的后缀s[i:]记...

ACM程序课算法笔记11——差分约束

ACM程序课算法笔记11——差分约束 差分约束方程组 差分约束指的是一种多个元素之间差的限制,而求某两个值的最大差。 例如求: x1 - x0 <= 2——① x2 - x0 <= ...