1 kmp 1 2 3 4 5 6 7 8 def kmp(s): nxt, i = [-1], -1 for c in s: while i>=0 and s[i]!=c: i = nxt[i] i += 1 nxt.append(i) return nxt # nxt[i]:i-1结尾的最大真前缀长度 2 manacher 1 2 3 4 5 6 7 8 9 10 11 12 13

线段树（Segment Tree）是一种二叉树形数据结构。多用于区间查询。 相比于 前缀和 和 树状数组， 线段树更复杂，也更通用。 线段树可以区间修改、

树状数组或二叉索引树（Binary Indexed Tree），又以其发明者命名为 Fenwick 树。 是一种解决动态数组区间查询问题的算法。 最简单的树状数组支持两种操作，

字典树，又叫前缀树，是一种 N 叉树，用于高效地存储、查找字符串前缀。 python 中可以用 defaultdict 来实现。 1 基础 0208 实现 Trie (前缀树) 0648 单词替换 2 进阶 0211 添加与搜索单

并查集（Union Find）也叫「不相交集合（Disjoint Set）」，是一种树型的数据结构， 专门用于 动态处理 不相交集合的「查询」与「合并

很多问题需要维护一个有序的集合，根据操作不同，可以选择更优的数据结构。 访问 搜索 插入 删除 访问最值 插入最值 删除最值 数组 list O(1) O(logN) O(N) O(N) O(1) O(1) O(1) 队列 deque O(N) O(N)

1 基础 0496 下一个更大元素 I 0739 每日温度 0901 股票价格跨度 2 进阶 0084 柱状图中最大的矩形 0085 最大矩形 0907 子数组的最小值之和 3 挑战 0456 132 模式 0962 最大宽度坡 0975 奇偶跳 1124

一些问题涉及到数学的几何知识，包括斜率、面积、凸包等。 相关的算法有 扫描线算法 等。 1 基础 0223 矩形面积 2 进阶 0149 直线上最多的点数 3 挑战 0335 路径交叉 *4 扫

一些问题涉及到数学的代数知识： 基础的四则运算、平方开根、进制转换等 排列组合、概率统计 数论知识，包括质数、同余、因式分解、乘法逆元等 1 运算 1.1 基

滚动哈希是一种针对固定长度的滑动窗口的哈希方法。 朴素的哈希需要对所有窗口单独求哈希值，时间复杂度和空间复杂度都和窗口长度相关。 用滚动哈希则可