【Data Structure】May

红黑树

红黑树是一种自平衡的二叉查找树，它在计算机科学中应用广泛，能保证在最坏情况下基本动态集合操作的时间复杂度为 O(log n)。下面从定义与性质、旋转操作、插入与修复、删除与修复、复杂度分析、以及实际应用等几个方面详细介绍。

1. 定义与基本性质

红黑树的每个节点除了包含关键字、左右孩子、父节点指针外，还带有一个颜色属性，取值为红色（RED）或黑色（BLACK）。
它必须满足以下五条红黑树性质：

节点是红色或黑色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
这里的叶子节点是指表示空的孩子节点，通常用一个黑色的哨兵节点 T.nil 代替，所有原本指向 NULL 的指针都指向它。
如果一个节点是红色，则它的两个子节点都是黑色。
也就是说，不允许出现两个连续的红色节点（即“红—红”父子关系）。
从任一节点到其每个叶子的所有简单路径上，包含相同数目的黑色节点。
该数目称为该节点的黑高（black-height），记为 bh(x)。整棵树的根节点的黑高定义为树的黑高。

这些性质保证了树的近似平衡：从根到最远叶子的最长可能路径长度不会超过最短可能路径长度的两倍。
证明思路：最短路径全为黑节点（长度 bh(root)），最长路径红黑相间（长度至多 2 * bh(root)），从而高度上限为 2 log₂(n+1)。

2. 红黑树的节点与结构

典型实现中定义一个哨兵节点 nil，颜色为黑，它的左右孩子和父指针可以指向自身或任意节点。所有原本是 NULL 的指针都指向 nil。根节点的父节点也是 nil。这样可以在处理边界时简化代码。

每个节点的属性通常包括：

key：关键字
color：RED 或 BLACK
left, right, p：指向左孩子、右孩子、父节点的指针

3. 旋转操作

为了维护红黑性质，插入和删除时会用到左旋和右旋，它们可以在 O(1) 时间内改变树的结构而不破坏二叉查找树性质。

左旋 (Left Rotate)：对节点 x 做左旋，假设其右孩子 y 不是 nil。
让 y 成为子树的新根，x 成为 y 的左孩子，y 原来的左子树变成 x 的右子树。
右旋 (Right Rotate)：对节点 y 做右旋，假设其左孩子 x 不是 nil。
让 x 成为子树的新根，y 成为 x 的右孩子，x 原来的右子树变成 y 的左子树。

旋转操作维持了中序遍历的顺序，是自平衡调整的基础。

4. 插入操作

红黑树的插入首先按照普通二叉查找树的插入方法，将新节点 z 插入并染成红色，然后调用 插入修复 过程 RB-Insert-Fixup(T, z) 以恢复红黑性质。

插入后可能违反的性质只有两条：

性质2：根节点必须是黑色（若 z 是根且染成红色则违反）；
性质4：红色节点的孩子必须是黑色（若 z 的父节点是红色则违反）。

修复过程的核心思想是不断向上移动冲突，主要通过考察 z 的叔节点 y（父节点的兄弟）的颜色进行分类处理：

循环条件：z.p.color == RED
在循环中设 z.p 是 z.p.p 的左孩子或右孩子，两种情形对称。以父节点是左孩子为例：

情况1：叔节点 y 是红色。
将父节点和叔节点都染黑，祖父节点染红，然后将 z 指向祖父节点继续向上修复。
这相当于把黑高度向下“推”了一层。
情况2：叔节点 y 是黑色，且 z 是父节点的右孩子。
将 z 指向父节点，并对新的 z 做左旋，转化为情况3。
情况3：叔节点 y 是黑色，且 z 是父节点的左孩子。
将父节点染黑，祖父节点染红，并对祖父节点做右旋。此时修复完成，循环终止。

循环结束后将根节点强制染黑，保证性质2。

插入时间复杂度：查找插入位置 O(log n)，修复过程每轮要么向上移动两层（情况1），要么最多执行两次旋转后终止（情况2+3），总共 O(log n)。因此插入为 O(log n)。

5. 删除操作

删除比插入更复杂。首先按二叉查找树的方式删除节点 z，记录被实际删除或移动的节点 y 及其颜色，并记录一个“替身”节点 x。

若 z 只有一个孩子或没有孩子，则 y = z；否则 y 是 z 的后继，y 的原始颜色被保存。
x 是 y 唯一的孩子（如果 y 有非 nil 孩子）或者是 nil（如果 y 没有孩子）。
若 y 的原始颜色为黑色，则删除或移动 y 会导致经过原来 y 的路径上黑节点数减少1，可能违反红黑性质，需要调用 删除修复 过程 RB-Delete-Fixup(T, x)。

删除修复的核心是通过 x 节点（它目前占据 y 原来的位置）“额外附带一层黑色”，即看作双黑色或红黑色，使路径黑高暂时得到补偿。修复过程逐步将这层额外黑色向上推移，或者通过旋转和变色消除它。

修复循环条件：x 不是根且 x.color == BLACK。在循环中根据 x 是其父节点的左/右孩子分对称情况，以 x 是左孩子为例：

设兄弟节点 w = x.p.right：

情况1：w 是红色。
将 w 染黑，x.p 染红，对 x.p 左旋，更新 w 为新的兄弟节点。转化为情况2、3或4。
情况2：w 是黑色，且 w 的两个孩子都是黑色。
将 w 染红，让 x 指向 x.p，把额外黑色向上一层。循环继续。
情况3：w 是黑色，w 的左孩子红色、右孩子黑色。
将 w.left 染黑，w 染红，对 w 右旋，更新 w。转化为情况4。
情况4：w 是黑色，w 的右孩子是红色。
将 w 的颜色设为 x.p 的颜色，x.p 染黑，w.right 染黑，对 x.p 左旋。此时额外黑色被完全消除，将 x 设为根以终止循环。

循环结束后将 x 强制染黑。

删除时间复杂度：查找后继等 O(log n)，修复最多进行三次旋转（情况1+情况4组合），循环最多 O(log n) 次（情况2上移），总体 O(log n)。

6. 复杂度分析与比较

空间复杂度：O(n)，每个节点存储颜色等常数额外信息。
查找、插入、删除：均为 O(log n) 最坏情况时间。
与 AVL 树相比：红黑树的平衡条件更弱（最长路径≤2倍最短路径），因此插入和删除时旋转次数通常更少（插入最多2次旋转，删除最多3次旋转），更适合写操作频繁的场景；AVL 树更严格平衡，查找稍快，但旋转开销较大。

7. 常见应用

标准库中的有序关联容器：
C++ STL 的 std::map、std::set、std::multimap、std::multiset 通常用红黑树实现；
Java 的 TreeMap、TreeSet 同样基于红黑树。
Linux 内核：完全公平调度器（CFS）用红黑树管理进程的虚拟运行时间；epoll 事件管理中也使用红黑树来快速查找文件描述符。
其他：实现定时器管理、区间树、一致性哈希中虚拟节点的组织等，凡需要动态维护有序数据且要求稳定 O(log n) 性能的场景，红黑树都是常用选择。

8. 总结

红黑树通过在二叉查找树上附加颜色属性并强制五条性质，用较少的旋转代价维持了近似平衡，保证了查找、插入、删除的最坏情况 O(log n) 性能。其设计巧妙地利用颜色约束和局部旋转，将破坏性质的影响控制在常数级调整范围内，是现代计算机系统中实现有序字典和有序集合的首选数据结构之一。

同构二叉树

在数据结构中，同构的二叉树（Isomorphic Binary Trees）是指：两棵二叉树可以通过交换某些节点的左右子树，最终变得结构和节点值完全相同。

简单来说，它们本质上是“镜像可互换”的等价树。

递归定义（判断标准）

两棵二叉树 (T_1) 和 (T_2) 同构，当且仅当满足以下任一条件：

均为空树。
根节点值相等，并且满足以下两种情况之一：
- (T_1) 的左子树与 (T_2) 的左子树同构，且 (T_1) 的右子树与 (T_2) 的右子树同构（不发生交换）。
- (T_1) 的左子树与 (T_2) 的右子树同构，且 (T_1) 的右子树与 (T_2) 的左子树同构（发生交换）。

注意：如果只要求结构相同而忽略节点值，则称为“结构同构”，上面说的是包含值的同构，是最常见的定义。

举例说明

树 A

    1
   / \
  2   3

树 B

    1
   / \
  3   2

这两棵树是同构的：根节点都是1，A的左(2)与B的右(2)同构，A的右(3)与B的左(3)同构——相当于交换了一次左右孩子就完全相同了。

树 C

    1
   /
  2

树 D

  1
   \
    2

它们也同构：根同值，C的左与D的右对应，空与空对应。

不同构的例子：

  1       1
 / \     / \
2   3   2   4

根值相同，但子树中3和4不等价，无论交不交换左右，都无法完全匹配，因此不同构。

与“相同/相等”二叉树的区别

相同（Identical）：不允许交换左右，结构必须完全一致，对应位置值相等。
同构（Isomorphic）：允许在任意节点处交换左右子树，使得最终能重合。

所以，同构的条件比相同更宽松。

常见应用

用于判断表达式树在满足交换律（如加法、乘法）时的等价性。
在某些编译优化或树匹配算法中，允许“无关顺序”的比较。

如果需要，我可以再展开讲判断同构的递归算法或时间复杂度的优化。

堆

堆是一种特殊的完全二叉树，常用数组存储。以最大堆为例，每个节点的值都大于或等于其子节点的值（最小堆则相反）。构建一个堆通常有两种方法：逐个插入法和从数组直接建堆（堆化）。下面分别详细介绍。

准备知识：堆的数组表示

假设数组下标从 1 开始（也可从0开始，以下均以1为例），节点 i 的：

父节点：⌊i/2⌋
左孩子：2i
右孩子：2i+1 堆要求除了最底层，其他层完全满，最底层节点靠左填充，因此数组中没有“空洞”。

方法一：逐个插入法（自顶向下构建）

这种方法从空堆开始，每次读入一个新元素，将它放到堆的末尾，然后通过**上浮（sift-up）**操作，让新元素不断与父节点比较并交换，直到满足堆的性质。

步骤

初始化空堆（数组为空或仅有哨兵）。
对于每个待插入的元素 val：
- 将 val 添加到数组末尾，size 加1，设当前位置 i = size。
- 上浮循环：当 i > 1 且 A[i] > A[i/2]（父节点）时，交换 A[i] 与 A[i/2]，然后 i = i/2，继续向上比较。
- 直到 A[i] ≤ A[i/2] 或 i == 1 时停止。

伪代码（最大堆）

Insert(A, val, size):
    size = size + 1
    A[size] = val
    i = size
    while i > 1 and A[i] > A[i/2]:
        swap(A[i], A[i/2])
        i = i / 2

时间复杂度

每次插入最坏要沿着树高走到底，树高 ⌊log₂n⌋，单次插入 O(log n)。
构建含有 n 个元素的堆，要进行 n 次插入，总时间 O(n log n)。
实际上，后期插入时堆已经较高，整体消耗近似为 n log n。

适用场景

数据流持续到来，无法事先知道全部元素，只能一个个加入。
在线算法、优先队列的动态增长。

方法二：从数组建堆（自底向上堆化，Floyd 建堆法）

如果事先已经拿到了所有元素，可以直接将整个数组当作一个未调整的完全二叉树，然后从最后一个非叶子节点开始，自底向上依次对每个节点执行**下沉（sift-down）**操作，一次性调整成堆。

步骤

将所有元素依次放入数组 A[1..n]（无须额外内存，就是原数组）。
找到最后一个非叶子节点的下标：start = ⌊n/2⌋。
对 i 从 start 下降到 1，依次调用 SiftDown(A, i, n)：
- 下沉操作：在 i 及其左右孩子中找出最大值，若最大值不是 i，则交换 i 与最大孩子，然后递归地对被交换的孩子继续下沉，直到满足堆性质或到达叶子。

伪代码（最大堆）

BuildHeap(A, n):
    for i = n/2 down to 1:
        SiftDown(A, i, n)

SiftDown(A, i, n):
    while 2*i <= n:          // 有左孩子
        maxIndex = i
        if A[2*i] > A[maxIndex]: maxIndex = 2*i
        if 2*i+1 <= n and A[2*i+1] > A[maxIndex]: maxIndex = 2*i+1
        if maxIndex == i:
            break            // 已满足堆性质
        swap(A[i], A[maxIndex])
        i = maxIndex        // 继续向下调整

为什么正确？

当对节点 i 执行下沉时，它的左右子树都已经是合法的堆（因为我们从下往上处理，先保证了子树是堆）。下沉操作相当于将 i 逐步下放到合适位置，之后以 i 为根的整个子树就变成了堆。处理完所有非叶子节点，整棵树就成了堆。

时间复杂度：O(n)

直观上可能会觉得每个节点最多下沉 O(log n) 次，总复杂度 O(n log n)，但精确分析发现是线性的。

高度为 h 的节点最多有 ⌈n/2^{h+1}⌉ 个，下沉的代价与高度 h 成正比。
总代价 ≈ Σ_{h=1}^{⌊log₂n⌋} h × (n / 2^{h+1}) = n/2 × Σ h / 2^h ≤ n/2 × 2 = n。所以总操作次数不超过 n 这个量级，因此建堆只需 O(n) 时间。

通俗理解：大部分节点都位于树的下层，它们下沉的距离很短；少量高层节点下沉距离长，但数量极少，总和有限。

适用场景

一次性拿到全部数据，需要快速构建堆。
堆排序的第一步（直接对数组建堆，再依次取出最值）。
批量加载数据到优先队列。

两种方法的对比

方法	逐个插入法	从数组建堆法（堆化）
方式	自顶向下，每次插入后上浮	自底向上，对非叶子节点下沉
时间复杂度	O(n log n)	O(n)
空间	需要动态扩容或预分配数组	原数组就地调整
使用条件	数据按顺序到达，未知总数	数据已全部给出，可随机访问
旋转次数	后期插入可能较多上浮交换	总体下沉交换次数更少

总结

逐个插入：灵活，适合动态场景，但构建效率较低，总时间 O(n log n)。
数组建堆：高效，利用完全二叉树的性质自底向上调整，时间复杂度仅为 O(n)，是批量构建堆的首选。

两种方法得到的堆可能不是同一个，但都满足堆的性质。理解了这两种构建方式，就能在实际开发中根据数据特点做出恰当选择。

哈夫曼树

哈夫曼树（Huffman Tree），也叫最优二叉树，是一种带权路径长度最短的二叉树。它由 David Huffman 在 1952 年提出，主要用于数据压缩，是哈夫曼编码的基础。

1. 核心概念

路径长度：从根到某节点所经过的边的数量。
带权路径长度（Weighted Path Length）：叶子节点的权值 (w_i) 乘以其路径长度 (l_i) 的总和。
整棵树的带权路径长度 (WPL = \sum_{i=1}^{n} w_i \times l_i)。
哈夫曼树：在叶子节点权值给定、内部节点不带权的情况下，WPL 最小的二叉树。

直观理解：权值越大的叶子，离根越近，这样乘出来的总和最小，就像用最“短”的路径去存储最“常用”的东西。

2. 构造算法（贪心策略）

哈夫曼树的构建使用自底向上的贪心算法，每次选择当前权值最小的两棵树合并。

步骤

将每个带权节点都看作一棵仅含根节点的二叉树，将它们放入一个集合（通常是最小堆/优先队列）。
重复以下过程，直到集合中只剩一棵树：
- 取出权值最小的两棵树 (T_1) 和 (T_2)。
- 创建一棵新树，新树的根节点权值为 (T_1.root.weight + T_2.root.weight)，左右孩子分别为 (T_1) 和 (T_2)。
- 将新树放入集合。
最后剩下的那棵树就是哈夫曼树。

实例演示

假设有 4 个叶子节点，权值分别为 {2, 3, 5, 7}。

初始：{2, 3, 5, 7}
取出 2 和 3，合并成权值 5 的新树，集合变为 {5, 5, 7}（注意有两个5）。
取出两个 5，合并成权值 10 的新树，集合变为 {7, 10}
取出 7 和 10，合并成权值 17 的新树，集合变 {17} —— 结束。

计算 WPL：
叶子 7 深度 1，叶子 5 深度 2，叶子 2 和 3 深度 3。
WPL = 7×1 + 5×2 + 2×3 + 3×3 = 7 + 10 + 6 + 9 = 32。
可以验证，任何其他结构的 WPL 都不小于 32。

3. 哈夫曼编码（前缀编码）

哈夫曼树最经典的应用是哈夫曼编码，用于无损数据压缩。

编码规则：从根出发，向左为 0，向右为 1，到达叶子时记录的 0/1 序列即为该叶子对应字符的编码。
特性：
- 每个字符的编码都是前缀码（任何一个编码都不是另一个编码的前缀），解码时不会出现歧义。
- 权值通常是字符出现频率，频率越高，编码越短，总编码长度接近理论最小值。

解码过程：从根开始，按比特流依次走 0/1，到达叶子即输出字符并回到根，继续解码。

4. 算法正确性证明思路

哈夫曼算法的正确性依赖于贪心选择性质和最优子结构：

贪心选择性质：权值最小的两个节点必定会作为深度最大的叶子被选中，可以互换不影响最优解，所以将它们合并不丢最优解。
最优子结构：合并两个最小节点得到的新频率，在剩下的问题中继续构建最优树，原问题的最优解包含子问题的最优解。

由此可证，按此贪心过程构造的树必定是 WPL 最小的二叉树。

5. 哈夫曼树的基本性质

共有 (n) 个叶子节点，则总节点数为 (2n - 1)。
没有度为 1 的节点，节点的度要么是 0（叶子），要么是 2（内部节点）。
叶子节点数 = 内部节点数 + 1。
同一组权值可能构造出结构不同但 WPL 相同的哈夫曼树（合并时若有平局，不同的选择可导致不同结构，但最优 WPL 唯一）。

6. 复杂度分析

使用最小堆（优先队列）实现：
- 初始建堆：(O(n))。
- 每次取最小两个元素和插入新元素：(O(\log n))，共进行 (n-1) 次合并。
- 总时间复杂度：(O(n \log n))。
空间复杂度：存储 (2n-1) 个节点的树，(O(n))。

7. 扩展：m 叉哈夫曼树

当需要构建 m 叉哈夫曼树（最优 m 叉树）时，需确保内部节点都能恰好有 m 个孩子，否则最后一轮合并可能缺少节点。解决方法：

当 ((n - 1) \bmod (m - 1) \neq 0) 时，补充若干个权值为 0 的虚拟叶子节点，使得上述余数为 0。
之后仍用类似贪心算法，每次合并最小的 m 个节点。

这种树常用于外排序中的多路归并、决策树优化等场景。

8. 应用场景

数据压缩：ZIP、JPEG、PNG 等格式底层都使用了哈夫曼编码。
通信编码：用最短的码字表示最常出现的消息。
文件合并与归并：最优 m 叉哈夫曼树用于确定多路归并的最佳合并顺序，减少 I/O 次数。
决策树：将概率作为权值，构造最优判定流程。

9. 总结

哈夫曼树是贪心算法在树形结构上的经典体现，通过反复合并最小权值节点，构造出带权路径长度最短的二叉树。它不仅理论优美，工程上更是数据压缩的核心组件。掌握哈夫曼树，也就掌握了“如何用最少的比特表达信息”的基本思想。

树

树（任意无环连通图）中，节点数 (n) 和边数 (e) 满足 (e = n - 1)，因此节点永远比边多 1。这是树最核心的性质之一，可以从两个角度来理解。

1. 直观理解：像“不断分叉的连线”

一棵树可以从单个节点开始“生长”出来：

只有 1 个节点时，0 条边，点比边多 1。
每次添加一个新节点，必须恰好连出一条边连接到已有树上的某个节点。
如果连出 0 条边，就不连通，不是树；如果连出 2 条或更多边，会形成环，也不符合树的定义。
因此，节点数每增加 1，边数也恰好增加 1。

整个过程始终保持 节点数 - 边数 = 1 的差额不变。当有 (n) 个节点时，边数自然就是 (n-1)。

2. 严谨证明：归纳法或“剥叶子”

数学归纳法：
设树有 (n) 个节点，边数为 (e(n))。

当 (n=1)，边数 0，满足 (e(1) = 1-1 = 0)。
假设任何 (n=k) 的树都有 (e=k-1)。
对一棵 (n=k+1) 的树，它至少有一片叶子（度数为1的节点）。删除这片叶子及其相连的边，剩下 (k) 个节点的树，由假设它有 (k-1) 条边。再把叶子加回来，节点数+1，边数+1，因此边数变成 (k)，仍然满足 (e = (k+1)-1)。

或者用连通+无环的约束来证明：
一棵连通图至少要有 (n-1) 条边才能把所有节点连起来。而如果无环，边数就不能再多于 (n-1)，否则任意额外一条边都会在两个已连通的节点间产生第二条路径，形成环。所以边数只能恰好是 (n-1)。

3. 在常见树结构中的应用

这个性质不仅适用于图论中的抽象树，也适用你之前了解的各种树形数据结构：

二叉树 / 红黑树 / 哈夫曼树：有 (n) 个节点的树，一定恰好有 (n-1) 条“父子边”。
堆的数组表示：索引从 1 开始，父子关系通过下标乘 2 定位，虽然没有显式存储边，但隐含的父子关系数量仍然是 (n-1)。
森林：(t) 棵树的森林则有 (n - t) 条边，每棵树内部依然各自满足点比边多 1。

简单一句话：树必须连通又无环，连通“最低消费”是 n-1 条边，无环“最多只能”是 n-1 条边，两者夹逼，边数只能是 n-1。

KMP

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它能在 O(n + m) 的时间内，在一个长度为 n 的文本串 S 中找出所有长度为 m 的模式串 P 的出现位置。其核心思想是：利用已经部分匹配的信息，保持主串指针不回溯，通过模式串自身的规律滑动模式串，从而减少重复比较。

1. 暴力匹配（Brute-Force）的痛点

暴力算法中，当 S[i] 与 P[j] 失配时，会将 i 回溯到 i - j + 2，j 重置为 1，重新开始比较。这导致最坏情况时间复杂度为 O(n*m)。例如 S = “AAAAA…B”，P = “AAAB”，每次都要比较到最后一个字符才知道不匹配，然后回溯大量位置。

KMP 要解决的问题就是：当失配发生时，如何在不回溯主串指针 i 的前提下，让模式串向右滑动尽可能远的距离。

2. KMP 的核心：部分匹配表（next 数组）

KMP 的精髓是一个被称为 next 数组（或前缀函数 π）的预处理表。对于模式串 P，next[j] 表示：在模式串的第 j 个字符发生失配时，模式串应该向右滑动多少位，或者说，接下来应该用模式串中的哪个字符继续与主串当前字符 S[i] 比较。

更精确的定义是：next[j] 等于 P[1..j-1] 这个子串中，既是真前缀又是真后缀的最长子串的长度。这个长度就是模式串在失配后可以“复用”的比较次数。

设模式串索引从 1 开始（便于叙述，编程中常用 0 起点），即 P = p1 p2 ... pm。

真前缀：不包含自身的前缀。
真后缀：不包含自身的后缀。

定义：对于 1 ≤ j ≤ m，next[j] = max{ k | 0 ≤ k < j-1 且 P[1..k] = P[j-k..j-1] }。当不存在这样的 k 时，next[j] = 0（若索引从 1 开始）或 -1（若索引从 0 开始）。我们用从 1 开始的版本讨论，并规定 next[1] = 0。

物理意义：若 p_j 失配，说明 p_1..p_{j-1} 与主串中 s_{i-j+1}..s_{i-1} 完全匹配。此时，p_1..p_{j-1} 的最长相等前后缀长度 k，就意味着模式串的前 k 个字符可以直接与主串的 s_{i-k}..s_{i-1} 对齐，而无需重新比较。于是下一次比较就是 p_{k+1} 与 s_i。

3. 构建 next 数组（递推法）

求 next 数组本身就是一个模式串自匹配的过程，时间复杂度 O(m)。采用双指针递推，非常巧妙。

设模式串 P[1..m]，next 数组定义同上。我们已知 next[1] = 0。假设已经计算出 next[1], next[2], ..., next[j]，现求 next[j+1]。

核心思想：考察 p_j 与 p_{next[j] + 1}（即当前最长相等前后缀的下一个字符）。

令 k = next[j]，表示 P[1..k] 是 P[1..j] 的最长相等前后缀。
比较 p_{k+1} 与 p_{j+1}：
- 若相等：则 next[j+1] = k + 1，因为前后缀都加长了一个字符。
- 若不相等：说明无法简单扩展，需要退而求其次，在更短的前缀中寻找。即令 k' = next[k]，再比较 p_{k'+1} 与 p_{j+1}，重复此过程，直到找到相等的字符或 k 退到 0。当 k=0 时，若 p_1 仍不等于 p_{j+1}，则 next[j+1] = 0。

这个回溯过程实际上是在利用已求的 next 值加速比较，保证整体 O(m)。

伪代码（索引从 1 开始，next[1]=0）：

getNext(P, m):
    next[1] = 0
    k = 0
    for j = 1 to m-1:    // 已知next[j]，求next[j+1]
        while k > 0 and P[k+1] != P[j+1]:
            k = next[k]   // 失配，回溯
        if P[k+1] == P[j+1]:
            k = k + 1
        next[j+1] = k

如果习惯编程时从 0 开始索引，通常让 next[0] = -1，模式串索引 0..m-1，定义略有差异，但本质相同。

4. KMP 匹配过程

有了 next 数组，就可以进行匹配。

设置主串指针 i = 1，模式串指针 j = 1。

当 j == 0 或 S[i] == P[j] 时，i 和 j 同时后移；
否则，j = next[j]，即保持 i 不动，模式串右移。

当 j == m+1 时，说明匹配成功，位置为 i - m。然后通常令 j = next[m]（如果还有 next[m+1] 则用 next[m+1]）继续寻找下一个匹配。

伪代码：

i = 1, j = 1
while i <= n:
    while j > 0 and S[i] != P[j]:
        j = next[j]
    if j == 0 or S[i] == P[j]:
        i++, j++
    if j == m+1:
        输出 i - m
        j = next[m]   // 或直接 j = next[j-1]? 实际处理：令 j = next[m] 继续

注意处理边界：为了方便，可设 next[1]=0，且当 j=0 时，表示模式串第一个字符就对不上，此时 i++，j=1（即下次比较 P[1] 与下一个字符），这与上面流程一致。

5. 举例演示

文本 S = “ABC ABCDAB ABCDABCDABDE”，模式 P = “ABCDABD”（长度为7）。

第一步：计算 next 数组（索引1~7）

next[1] = 0
j=1 (k=0): 比较 P[2]=‘B’ 与 P[1]=‘A’? 不等，且 k=0 => next[2]=0
j=2 (k=0): 比较 P[3]=‘C’ 与 P[1]=‘A’? 不等 => next[3]=0
j=3 (k=0): 比较 P[4]=‘D’ 与 P[1]=‘A’? 不等 => next[4]=0
j=4 (k=0): 比较 P[5]=‘A’ 与 P[1]=‘A’? 相等 => k=1, next[5]=1
j=5 (k=1): 比较 P[6]=‘B’ 与 P[2]=‘B’? 相等 => k=2, next[6]=2
j=6 (k=2): 比较 P[7]=‘D’ 与 P[3]=‘C’? 不等，k=next[2]=0；再比较 P[7]=‘D’ 与 P[1]=‘A’? 不等且k=0 => next[7]=0

所以 next = [0,0,0,0,1,2,0] (索引1~7)

第二步：匹配过程

i=1,j=1 开始比较： S[1]=‘A’ = P[1] => i=2,j=2 S[2]=‘B’ = P[2] => i=3,j=3 … 直到 i=4,j=4: S[4]=’ ’ != P[4]=‘D’，失配，j=next[4]=0。然后 i++, j=1（因为 j=0 时相当于 j=1，i 已经指向下一字符）
i 走到文本中的第一个 “ABCDAB” 处，会匹配到 j=6 (字符’B’匹配)，然后 i 前进到后面的空格 ’ ‘，模式串 j=7 应为 ‘D’，失配。j = next[7]=0，i 跳过空格。
最终 i 走到 “ABCDABD” 位置，完全匹配，输出位置。

这里展现了 next 数组如何帮助跳过无用的比较。

6. 时间复杂度分析

预处理 next 数组：循环 j 从 1 到 m-1，每次循环中 while 循环内 k 的值至少减小 1，而 k 总共增加次数不超过 m（每次 if 增加1），所以 while 总执行次数 O(m)。因此预处理 O(m)。
匹配过程：同理，i 从 1 到 n，指针 j 增加次数不超过 n，while 中 j = next[j] 每次至少减少 1，所以总比较次数 O(n)。
总时间复杂度 O(n + m)。

空间复杂度 O(m)（存储 next 数组）。

7. next 数组的优化（KMP 的改进）

标准 next 数组有时仍会有多余比较。例如模式串 “AAAB”，当 P[j] 失配且 P[next[j]] 与 P[j] 相同时，用 next[j] 去匹配必然再次失配。可引入 nextval 数组：如果 P[j] == P[next[j]]，则 nextval[j] = nextval[next[j]]，否则 nextval[j] = next[j]。这样进一步加快失配时的跳转。

8. 应用与扩展

字符串查找：文本编辑器的“查找”功能。
生物信息学：基因序列比对。
网络入侵检测：模式匹配过滤。
扩展算法：AC 自动机（KMP 的多模式版本）、BM 算法（从右向左匹配）等。

KMP 算法将“记忆”引入字符串匹配，是算法设计中利用已有信息避免重复计算的经典范例。理解了 next 数组的构建原理，也就掌握了 KMP 的灵魂。

BM

BM（Boyer-Moore）算法是一种高效的字符串匹配算法，由 Boyer 和 Moore 于 1977 年提出。它打破了“从左向右逐个比较”的惯性，采用从模式串末尾向前匹配的方式，并借助坏字符规则和好后缀规则两种启发式策略，使模式串能够以更大的步幅跳跃，避免了大量无意义的比较。在实际应用中（尤其是长模式和大字符集），BM 算法往往比 KMP 算法快得多，许多文本编辑器、搜索引擎的查找功能底层都曾使用它。

1. 核心思想：从右向左 + 双重跳跃

匹配方向：将模式串 (P) 与文本串 (T) 对齐后，从 (P) 的最后一个字符开始向前比较。
失配处理：当在某个位置发生字符不匹配时，根据失配处得到的两个信息计算模式串可以向右滑动的距离：
1. 坏字符规则：看文本中那个“对不上的字符”在模式串中出现的最后位置。
2. 好后缀规则：看已经匹配成功的那部分后缀在模式串中有没有别的出现位置。
取两种规则给出的滑动距离的最大值，让模式串一次性向右移动多位，主串指针从不回溯。

2. 坏字符规则（Bad Character Rule）

当比较时发现 (T[i] \neq P[j])，即 (P[j]) 与 (T[i]) 失配，此时称 (T[i]) 为坏字符。

规则：在模式串 (P) 中，找到坏字符 (T[i]) 从右往左最后一次出现的位置 (k)（且 (k < j)，即只能在当前失配位置的左侧寻找），然后将模式串向右移动 (j - k) 个位置，让 (P[k]) 与 (T[i]) 对齐。如果坏字符在 (P[0..j-1]) 中没有出现，则 (k = -1)，移动 (j + 1) 位，使整个模式串跳过这个坏字符。

预处理：构建“坏字符表”bc[字符]，记录每个字符在模式串中的最右位置（若字符不在模式串中则为 -1）。该表大小与字符集有关（如 ASCII 256、Unicode 可使用哈希表）。构建只需扫描一遍模式串，时间 (O(m+|\Sigma|))。

例子：模式串 P = "EXAMPLE"，文本 T = "HERE IS A SIMPLE EXAMPLE"。
当对齐到某位置，从后往前比较到 P[6]='L' 与 T 中的某个字符失配，假设坏字符是 'P'（在文本中）。查表 bc['P'] 在模式串中位置为 4（'P' 在 P[4]）。失配位置 j = 6，移动距离 6 - 4 = 2，让 P[4] 的 'P' 与文本的 'P' 对齐。

3. 好后缀规则（Good Suffix Rule）

失配发生时，已经成功匹配的部分（即 (P[j+1..m-1])）被称为好后缀，记作 suffix。好后缀规则利用了这个后缀的重复出现信息，进一步增大跳跃。

规则：将模式串向右滑动，使得：

情况1：好后缀 suffix 在模式串中再次出现（且不是当前位置）。即找到一个最大的 (k < m-1)，使得子串 (P[k - |suffix| + 1 .. k]) 与 suffix 完全相同，并且这个子串的左侧字符（(P[k - |suffix|])）不与失配字符相同（避免不必要的重新比较）。此时移动距离为 ( (m - 1) - k )（让找到的后缀对齐）。
情况2：如果好后缀在模式串中没有再次出现，则寻找好后缀的某一个后缀，使它等于模式串的某个前缀（最长匹配）。移动距离为 ( m - \text{该前缀长度} )，让模式串前缀与文本中已匹配的后缀部分对齐。
如果都不满足，则移动整个模式串长度 (m)。

预处理：好后缀的移动表通常记为 bmGs，长度为 (m+1)（对应好后缀长度从 0 到 m）。计算过程需要两个辅助数组：

suffix[i]：以 i 为结尾的子串与模式串后缀匹配的最大长度。
prefix[i]：布尔值，表示长度为 i 的模式串后缀是否也是模式串的前缀。

构建这两个数组只需 (O(m)) 时间。之后填充 bmGs：

先全部用 (m) 填充（默认移动整个模式串）。
根据 suffix 处理“好后缀再次出现”的情况，设置对应移动距离。
再处理“好后缀的部分与模式串前缀匹配”的情况，从后向前更新。

最终，当失配发生在位置 j，好后缀长度为 good_len = m - 1 - j，则移动距离 = bmGs[good_len]。

4. 完整匹配流程

预处理：计算坏字符表 bc 和好后缀表 bmGs。
开始匹配，i = m - 1（文本窗口右侧对齐），j = m - 1（模式串末尾）。
从右向左比较：
- 若 j >= 0 且 T[i] == P[j]：i--, j--，继续比较前一个字符。
- 若 j < 0：匹配成功，记录位置，并按 bmGs[0]（好后缀长度为 0 时的移动值）移动模式串。
- 否则（失配）：
  - 坏字符移动距离：bc[T[i]] 为坏字符最右位置，bad_move = j - bc[T[i]]（若 bc 返回 -1 则 bad_move = j + 1）。
  - 好后缀移动距离：good_move = bmGs[m - 1 - j]（失配位置 j 对应的好后缀长度）。
  - 取 max(bad_move, good_move) 作为模式串右移量，并相应更新 i 和 j（通常 i 增加移动量，j = m - 1 重新从末尾开始比较）。

5. 实例演示

文本：HERE IS A SIMPLE EXAMPLE
模式串：EXAMPLE (长度 m=7, 索引 0..6)

坏字符表（部分）：E:6, X:1, A:2, M:3, P:4, L:5，其他字符为 -1。
好后缀表（示例省略详细构建，直接给出）：
bmGs[0]=1（匹配成功后移动1，也可以按坏字符移动等），bmGs[1]=7, bmGs[2]=7, ...

匹配过程：

首次对齐：模式串从文本第0个字符开始，末尾 P[6]='E' 与文本第6个字符 ' ' 比较，失配。
- 坏字符 ' ' 不在模式串，bad_move = 6 - (-1) = 7。
- 好后缀长度为0，good_move = bmGs[0]=1（通常好后缀长度为0时移动1，但取 max 还是7）。
  模式串右移7位，跳过整个“HERE IS”。
继续比较，略过中间步骤，最终会在 ... SIMPLE EXAMPLE 处对齐：
模式串末尾 E 与文本中 E 匹配，然后向前依次匹配 L-P-M-A-X-E，全部成功，输出匹配位置。

整个过程中，许多比较被成段跳过，远远少于暴力法。

6. 复杂度分析

预处理：坏字符表 (O(m+|\Sigma|))，好后缀表 (O(m))，总 (O(m+|\Sigma|))。
匹配阶段：
- 最好情况：每次失配都发生在模式串最后一个字符，且坏字符不在模式串中，每次移动 (m) 位，比较次数为 (O(n/m))。
- 最坏情况：理论最坏 (O(n \cdot m))（例如文本 "aaaaa..."，模式 "baaa" 时会退化），但通过好后缀与坏字符的结合，实际工程中极少出现；一些改进版本（如 BMH、BMHS）可避免此退化。
- 平均情况：通常认为是亚线性的，实际运行极快。

对比 KMP：KMP 保证 (O(n+m)) 线性时间且与字符集大小无关，从左向右匹配；BM 一般更快，但需要额外空间存储字符集表，最坏时间无理论保证（原始版本）。现代混合算法常结合两者优势。

7. 常见变体与应用

Boyer-Moore-Horspool (BMH)：简化版，仅使用坏字符规则的一个变体（以文本窗口最后一个字符作为坏字符），实现简单且在实际中非常高效，是许多函数库（如 Python 的 find 曾用）的默认选择。
Boyer-Moore-Sunday：进一步优化，检查窗口右侧下一个字符决定移动。
应用：GNU grep、各种文本编辑器的查找替换、网络入侵检测系统（如 Snort）的模式匹配引擎。

8. 总结

BM 算法通过“向后看”的独特视角和两条强有力的跳跃规则，将字符串匹配的效率推向了极致。它启示我们：在看似必须逐个推进的问题中，充分利用已比较信息并摆脱固定扫描方向，往往能发现巨大的优化空间。掌握 BM 算法，不仅是学习了一种匹配技巧，更是对如何设计智能启发式跳跃以达成亚线性计算的一次深刻认知。

Sunday

Sunday 算法是 Daniel M. Sunday 在 1990 年提出的一种字符串匹配算法。它属于 Boyer-Moore 算法家族，可以看作是 Boyer-Moore-Horspool 的改进版，核心区别在于：Sunday 算法在发现不匹配时，关注当前对齐窗口的下一个字符（而不是窗口内的失配字符或末尾字符），并以此决定模式串的移动距离。这一策略往往能获得更大的跳跃步长，且实现极为简洁，在多数实际场景中效率极高。

1. 核心思想

将模式串 P（长度为 m）与文本串 T（长度为 n）的某个位置对齐，假设窗口起始索引为 i，即对齐 T[i … i+m-1]。
从左向右逐个字符比较 T[i+j] 与 P[j]（j = 0,1,…,m-1）。
若完全匹配，则记录位置；若发生失配，则立即查看文本中紧接着当前窗口的下一个字符 ch = T[i+m]（即窗口外右侧第一个字符）。
根据该字符在模式串中最后一次出现的位置，计算出模式串向右滑动的距离，使得这个字符能够与模式串中对应的位置对齐。
然后从新的窗口重新开始比较。

因为每次失配后直接利用 T[i+m] 来决定位移，不需要维护类似 BM 算法中的“好后缀”规则，也不关心窗口内已匹配了哪些字符，所以算法逻辑非常简单。

2. 预处理：构建偏移表 `shift`

需要事先计算一个偏移表 shift，存储规则是：对于字符集中的所有字符 c，定义：

如果 c 在模式串 P 中出现，则 shift[c] = m - max{k | P[k] == c}（即 c 在 P 中最右边出现位置到末尾的距离）；
如果 c 未在 P 中出现，则 shift[c] = m + 1。

使用伪代码描述如下（假设字符集大小为 256，索引从 0 开始）：

// 初始化所有字符的移动距离为 m+1
for c in 字符集:
    shift[c] = m + 1

// 扫描模式串，用较短的移动距离覆盖
for k from 0 to m-1:
    shift[P[k]] = m - k

因为从左向右扫描，后面的相同字符会覆盖前面的值，所以最终 shift[c] 保留的是最右侧出现对应的最小移动距离。这个表只需要构建一次，时间复杂度 (O(m + |\Sigma|))。

3. 匹配过程

主串指针 i 从 0 开始，不断尝试将模式串放在 i 处进行比较。

i = 0
while i <= n - m:
    j = 0
    // 从左向右比较
    while j < m and T[i+j] == P[j]:
        j++
    if j == m:
        记录匹配位置 i
        // 匹配成功后如何移动？可以继续用 shift 表
        // 一般看窗口后一个字符决定下一跳
        if i + m < n:
            i += shift[T[i+m]]
        else:
            break
    else:
        // 失配：查看窗口后的字符
        if i + m < n:
            i += shift[T[i+m]]
        else:
            break   // 已超出文本范围，无法继续

注意边界：当 i + m == n 时，窗口已顶到文本末尾，不存在“下一个字符”，此时如果发生失配或完成匹配，可直接结束循环。

4. 实例演示

文本 T = "substring searching"
模式串 P = "search"，长度 m = 6。

首先计算偏移表（为简洁，只列出模式串中出现的字符）：

s：最右出现位置 0 → shift['s'] = 6 - 0 = 6
e：位置 1 → 6 - 1 = 5
a：位置 2 → 6 - 2 = 4
r：位置 3 → 6 - 3 = 3
c：位置 4 → 6 - 4 = 2
h：位置 5 → 6 - 5 = 1 其他字符（如空格、u, b 等）未出现，shift = 7。

匹配步骤：

i = 0，窗口 T[0..5] = "substr"，与 "search" 比较。
j=0，'s' == 's'；j=1，'u' != 'e' → 失配。
窗口后字符 T[6] = 'i'，shift['i'] = 7，i = 0 + 7 = 7。
i = 7，窗口 T[7..12] = "ing se"，与 "search" 比较。
j=0，'i' != 's' → 失配。
窗口后字符 T[13] = 'a'，shift['a'] = 4，i = 7 + 4 = 11。
i = 11，窗口 T[11..16] = " search" （注意前面有个空格，T[11] 是空格，T[12]='s'…实际上 T = "substring searching"，索引从0：s u b s t r i n g s e a r c h i n g。
T[11] 是空格，T[12] 是 s，T[13] 是 e… 等等。窗口为 " searc"，而模式串是 "search"。
比较：j=0，空格 ≠ 's' → 失配。
窗口后字符 T[17] = 'h'，shift['h'] = 1，i = 11 + 1 = 12。
i = 12，窗口 T[12..17] = "search"，与模式串完全匹配！记录位置 12。
匹配后，查看下一个字符 T[18] = 'i'，shift['i'] = 7，i = 12 + 7 = 19。
此时 19 > 17（n - m = 23 - 6 = 17），循环结束。

整个过程仅跳跃了 4 次，比较次数很少，窗口后的字符帮助大幅跳过了不可能匹配的区域。

5. 复杂度分析

预处理：遍历模式串和字符集，时间复杂度 (O(m + |\Sigma|))，空间复杂度 (O(|\Sigma|))（可存储完整字符集或仅用哈希表记录出现过的字符）。
匹配阶段：
- 最好情况：每次失配发生在模式串第一个字符，且 T[i+m] 不在模式串中，每次直接移动 m+1 位，时间复杂度 (O(n / m))。
- 最坏情况：与 BM 类似，某些特定模式串和文本组合（如 P = "baaa", T = "aaaaaa..."）可能导致多次仅移动 1 步，复杂度退化至 (O(n \cdot m))。但在实际自然语言文本中极罕见。
- 平均情况：通常认为 Sunday 算法具有亚线性平均性能，往往比 BM 和 KMP 更快，尤其在大字符集（如 Unicode）下优势明显。

6. 与 Horspool、Boyer-Moore 的区别

算法	失配后关注的字符	移动依据	预处理复杂度
BM	窗口内失配的字符 + 好后缀	坏字符规则与好后缀规则取最大值	(O(m+
Horspool	当前窗口的最后一个字符 `T[i+m-1]`	该字符在模式串中的最右位置	(O(m+
Sunday	窗口后的下一个字符 `T[i+m]`	该字符在模式串中的最右位置	(O(m+

Sunday 算法关注的是尚未参与比较的那个字符，这使得它经常能比 Horspool 移动得更远。例如当窗口内所有字符都匹配成功，但窗口后字符恰好不在模式串中时，Sunday 可以直接移动 m+1 位，而 Horspool 只能利用窗口末尾字符，可能移动距离较小。此外，Sunday 不需要像 BM 那样维护复杂的好后缀表，代码量显著减少。

7. 实际应用与变种

快速文本搜索：许多软件和库（如某些语言运行时的 indexOf / find 函数）会采用 Sunday 算法或类似变体。
网络入侵检测：在 Snort 等系统中，多模式匹配引擎也会借鉴 Sunday 的快速跳跃思想。
变种：由于 Sunday 算法极其简洁，很容易扩展为忽略大小写、多模式匹配等版本。有论文提出结合 KMP 的 next 数组优化最坏情况，但通常工程上更倾向接受其极佳的平均性能。

8. 总结

Sunday 算法用极简的规则——“失配时看窗口后一个字符”——实现了字符串匹配的快速跳跃。它避免了复杂的回溯和好后缀计算，将预处理压缩为一维数组，匹配过程流畅且高度可优化。正因为这种简单与高效，Sunday 算法成为字符串搜索领域最实用的算法之一，也是理解 BM 算法族思想的一个绝佳切入点。

选择排序

选择排序（Selection Sort） 是一种简单直观的比较排序算法。它的基本思路是：将数组分为已排序和未排序两部分，每轮从未排序部分选择最小的元素，放到已排序部分的末尾，直至整个数组有序。

1. 核心思想

划分区间：整个数组被分为 [0, i-1]（已排序）和 [i, n-1]（未排序）两段。初始时 i=0，已排序部分为空。
选择最小：在第 i 轮（i 从 0 到 n-2），遍历未排序区间 [i, n-1]，找出最小元素。
交换到位：将这个最小元素与位置 i 的元素交换。此时位置 i 上的元素归位，已排序区间扩大到 [0, i]。
重复这个过程，直到 i 到达 n-1（最后一个元素自然就位）。

2. 算法步骤（升序为例）

对于长度为 n 的数组 arr：

从 i = 0 开始，直到 i = n-2：
- 设置 minIndex = i。
- 对于 j 从 i+1 到 n-1：
  - 如果 arr[j] < arr[minIndex]，则更新 minIndex = j。
- 如果 minIndex != i，交换 arr[i] 与 arr[minIndex]。
结束。

示例：数组 [64, 25, 12, 22, 11]

第1轮：找到最小元素 11，与 64 交换 → [11, 25, 12, 22, 64]
第2轮：在 [25,12,22,64] 中找到最小 12，与 25 交换 → [11, 12, 25, 22, 64]
第3轮：找到最小 22，与 25 交换 → [11, 12, 22, 25, 64]
第4轮：找到最小 25，已在正确位置，不交换。
结束，数组有序。

3. 代码实现

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

C++

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

4. 复杂度分析

项目	情况
时间复杂度
最好情况	(O(n^2))
最坏情况	(O(n^2))
平均情况	(O(n^2))
空间复杂度	(O(1))（原地排序）

无论输入数据是否接近有序，比较次数固定为 (\frac{n(n-1)}{2})，因此时间复杂度恒为 (O(n^2))。
交换次数：最坏需要 (n-1) 次交换，最好为 0 次（已排序且无相等时）。

5. 稳定性

选择排序是不稳定的排序算法。
因为交换操作可能会跨越相等的元素，破坏原有的相对顺序。

示例：数组 [5, 8, 5, 2, 9]，稳定排序应保持两个 5 的先后。
第1轮找到最小值 2，与 arr[0]=5 交换，数组变为 [2, 8, 5, 5, 9]，第一个 5 被换到了相对靠后的位置，改变了两个 5 的原始顺序。

6. 特点与适用场景

优点：

实现极其简单，易于理解。
无需额外内存（原地排序）。
交换次数少（最多 (n-1) 次），适用于写操作成本很高的场景（如 Flash 存储）。

缺点：

时间复杂度高，不论输入如何都是 (O(n^2))，数据量大时效率极低。
不稳定。

适用场景：

数据规模很小（如几十个元素）且对性能要求不高的场合。
对交换次数有严格限制的存储介质。
作为其他复杂算法（如堆排序、快速排序）的退化处理或教学演示。

7. 与其他简单排序的对比

算法	时间复杂度	空间复杂度	稳定性	特点
选择排序	(O(n^2))	(O(1))	不稳定	交换次数最少
冒泡排序	(O(n^2))	(O(1))	稳定	可通过检测提前终止，适合基本有序
插入排序	(O(n^2))	(O(1))	稳定	对于部分有序数据效率很高

选择排序的优势在于思路直观和极少的数据移动次数，但由于时间复杂度的根本限制，它很少用于大型数据集。不过，理解选择排序是学习更高效排序算法（如堆排序，其本质是选择排序的优化）的重要基石。

广义表

广义表（Generalized List），也称列表，是线性表的一种推广。它的特殊之处在于：表中的元素既可以是单个数据元素（原子），也可以是一个广义表（子表）。这种递归定义使得广义表能灵活地表达层次化、嵌套的数据结构。

1. 定义

广义表是 n (n≥0) 个元素的有穷序列，记为：

LS = (d₁, d₂, …, dₙ)

其中：

原子：当 dᵢ 是单个不可再分的数据元素时，称 dᵢ 为原子，通常用小写字母表示。
子表：当 dᵢ 本身又是一个广义表时，称它为 LS 的子表，通常用大写字母表示。
n 为表长。 n=0 时称为空表。

递归定义：广义表可以由原子和已经定义好的广义表构造而成。

例子：

A = () —— 空表，长度 0。
B = (a, (b, c)) —— 长度为 2，第一个元素是原子 a，第二个元素是子表 (b, c)。
C = (a, B, (c, d)) —— 长度为 3，原子 a、子表 B、子表 (c, d)。
D = (A, B, C) —— 长度为 3，三个元素都是子表。
E = (a, E) —— 长度为 2 的递归表，第二个元素是表自身（无穷深）。

2. 重要术语

长度：广义表第一层元素的个数（原子和子表都算一个元素）。
深度：广义表括号嵌套的最大层数。原子的深度为 0，空表的深度为 1。例如：
- (a, (b, c)) 的深度为 2。
- (a, (b, (c, d))) 的深度为 3。
- 递归表 (a, E) 的深度为无穷大。
表头（Head）：广义表非空时的第一个元素，可以是原子或子表。
表尾（Tail）：去掉表头之后，由其余元素组成的广义表（注意：表尾一定是个广义表，哪怕只剩一个元素也要加括号）。
- 例如 LS = (a, (b, c), d)，Head(LS) = a，Tail(LS) = ((b, c), d)。
递归表：广义表在定义时直接或间接地包含自身。

3. 存储结构

由于元素类型不统一、大小不固定，广义表无法用简单的顺序结构存储，普遍采用链式存储。有两种典型表示法：

① 头尾链表表示法

每个结点对应一个元素，结点包含：

tag 标志位：0 表示原子，1 表示子表。
如果 tag=0，结点存储原子值和一个指向下一个元素的指针。
如果 tag=1，结点存储两个指针：指向子表表头的指针 (hp) 和指向同一层下一个元素的指针 (tp)。

这种结构自然地表示了表头、表尾的分解关系。

② 扩展线性链表表示法

结点结构类似，但把同层元素用单链表串联起来：

tag=0：原子结点，含数据和 next 指针。
tag=1：子表结点，含一个指向子表的指针和 next 指针。

这种方式更适合需要方便遍历同一层全部元素的场景。

4. 基本操作

广义表支持的操作通常有：

Head(L)：取表头。
Tail(L)：取表尾。
Length(L)：求长度。
Depth(L)：求深度。
Copy(L)：复制广义表。
Create/Insert/Delete：构造、插入、删除元素（涉及内存管理）。

所有操作几乎都是递归定义的，例如求深度的递归算法：

若表为空，深度=1；若为原子，深度=0；
否则，深度 = 1 + max{各子表的深度}。

5. 与线性表的区别

线性表	广义表
所有元素类型相同，都是原子	元素可以是原子或广义表
结构是线性的	结构是分层的、递归的
长度是直接元素个数	长度是最外层元素个数，另有深度概念
顺序或链表存储	通常只能用链式结构

6. 应用场景

LISP / Scheme 语言：其核心数据结构就是广义表，用 S-表达式表示程序和数据。
多元多项式表示：例如 P(x,y) = 3x²y + 5xy³ 可以表示为广义表 ((3,2,1), (5,1,3))，每个子表表示系数和指数对。
稀疏矩阵：每一行的非零元素构成一个子表，各行再组成广义表，节省空间。
人工智能与符号处理：知识表示、树和图结构的通用描述。

7. 总结

广义表是一类极其灵活的数据结构，它打破了线性表元素必须为原子的限制，通过递归定义实现了嵌套。它以链式存储为基础，通过“表头-表尾”的分解方式统一处理原子和子表，在程序语言设计和复杂结构化数据的存储中扮演着重要角色。理解广义表，是理解递归数据结构、掌握 Lisp 系语言和进行复杂符号运算的关键一步。

贪心 & 动态规划

贪心算法和动态规划的核心区别，确实可以形象地概括为：贪心“绝不回头看”，动态规划“需要反复权衡过去和未来的所有可能”。这个说法抓住了两种算法哲学的根本不同。

下面详细拆解这个核心区别，并给出具体实例。

1. 决策方式的本质差异

维度	贪心算法 (Greedy)	动态规划 (Dynamic Programming)
决策视角	只看当前，选择眼下最优的局部解	统筹全局，考虑所有可能的划分和组合
状态依赖	不依赖未来信息，也不比较不同选择的历史	依赖于子问题的解，将大问题分解为重叠的子问题，并记录每个子问题的最优解
是否“回头看”	否。一旦做出选择，就永久固化，不再回溯或修改	是。通过记录每个状态的解，实际上是在“回顾”之前决策的后果，并在多个选项中选出真正最优的路径。它不是单步决策，而是多阶段决策的最优组合
正确性保证	需要严格的数学证明（如贪心选择性质、最优子结构）	满足最优子结构和重叠子问题即可，通过状态转移方程穷举所有可能

形象比喻：
贪心就像走一条单行道，在每个岔路口只凭当前路牌选择最宽的路，走了就不回头，哪怕后来发现走进了死胡同。
动态规划则像带着地图和记事本，走之前先研究所有可能的路线，或者边走边记下“从某个路口到终点的最短耗时”，最终选出一条真正最短的路。它的“回头看”体现在：回头审视之前记录的所有子问题的最优解，从而做出此刻最正确的选择。

2. 实例对比：找零钱问题

假设硬币面值有 {1, 5, 11} 三种，要凑出总金额 15，要求硬币数量最少。

贪心策略（“绝不回头看”）

每一步就选面值最大且不超过余额的硬币。

第一步：15 元，可选 11，剩下 4。
第二步：4 元，最大可选 1，选 1，剩下 3。
第三步：3 元，选 1，剩下 2。
第四步：2 元，选 1，剩下 1。
第五步：1 元，选 1，结束。结果：11 + 1 + 1 + 1 + 1 = 5 枚硬币。

贪心没有回头，首次选了 11 就再也无法改变，尽管这个选择导致了全局不是最优。

动态规划（“反复权衡过去”）

定义 dp[i] 为凑出金额 i 的最少硬币数。考虑递推式：

dp[i] = min( dp[i - coin] + 1 )  对于每个面值 coin ≤ i

计算 dp[15] 时，会参考 dp[14], dp[10], dp[4] 等所有已记录的子问题解：

若用 1 元：dp[15] = dp[14] + 1 = 4 + 1 = 5
若用 5 元：dp[15] = dp[10] + 1 = 2 + 1 = 3 （dp[10] 最优是 5+5）
若用 11 元：dp[15] = dp[4] + 1 = 4 + 1 = 5 DP 发现选 5 元可以得到全局最优，于是记录 dp[15]=3（即 5+5+5）。

这就是“回头看”的体现：dp[15] 在做决定时，并不是只看眼下的“补 4 元、补 10 元、补 4 元”哪个更小，而是调用了 dp[10] 等过去已经记录好的最优结果，综合比较后才做出选择。实际上它把曾经“选 10 元怎么选最优”的整个历史都考虑进来了，相当于反复权衡了所有可能的路径。

3. 再例：0-1 背包问题

有 3 件物品：①重量 1，价值 6；②重量 2，价值 10；③重量 3，价值 12。背包容量 5。

贪心（按单位价值排序，绝不回头）：
单位价值：①=6，②=5，③=4。
先拿①（剩余容量4），再拿②（剩余容量2），再拿③时放不下了。总价值 = 6+10 = 16。
贪心一旦选了 ① 和 ②，就不会回头重新考虑“是不是不拿 ② 而拿 ③ 更好”。
动态规划（记录所有子问题）：
状态 dp[i][w] 为前 i 件物品在容量 w 下的最大价值。计算时，它会考虑拿或不拿每件物品，并回顾之前的 dp 值。
dp[3][5] 会比较：
- 不拿 ③：dp[2][5] = 16
- 拿 ③：dp[2][2] + 12 = (6 + 10? 等等，dp[2][2] 实际是只拿 ① 可得 6，所以是 6+12 = 18
  结果 dp[3][5] = 18（拿 ① 和 ③）。
  动态规划通过回顾 dp[2][2] 这个过去的记录，发现了放弃物品 ② 反而更好的方案。

4. 为什么动态规划不是真正“撤销”决策？

需要澄清一点：动态规划并不会去改变已经写入表格的数值，它没有修改历史决策，而是在作出当前决策时，已经预见了未来的影响，或者说把历史当作参考。它通过 “状态” 保留了所有可能决策分支的后果，最后通过回溯/填表得到最优路径。

所以说“回头看”是指它反复利用过去计算出的子问题最优解来推导当前最优解，这是一种“向后看”的过程，而非后悔并重新选择。贪心则完全不利用那些没走过的路的信息。

5. 总结：一张表看懂“是否回头看”

特性	贪心	动态规划
做决策时是否回顾以前的方案？	从不	不断回顾（子问题的解）
是否在多种可能中做选择？	只选当前局部最优，不比较	全局比较所有可能划分
发现当前选择不好能否反悔？	不能	实际通过记录所有状态，隐式地“反悔”（选择另一条分支）
需要存储过去的信息吗？	只需记住上一个决策	需要表或备忘录存储子问题解
适用问题的特征	贪心选择性质（局部最优→全局最优）	重叠子问题 + 最优子结构

因此，“贪心不回头，动态规划反复权衡历史并综合决策” 是对两者核心区别既准确又通俗的概括。理解这一点，就能很快判断一个新问题该用哪种策略求解。

贪心选择性质

贪心选择性质是贪心算法得以成立的核心条件，也是区分一个优化问题能否用贪心策略求解的关键标志。

1. 定义：什么是贪心选择性质？

贪心选择性质（Greedy-choice property） 是指：

一个问题的全局最优解，可以通过一系列局部最优选择来达到。换句话说，每次我们做出在当前看来最好的选择（贪心选择），然后对产生的子问题继续进行贪心选择，最终就能得到整个问题的最优解。

更形式化地：

设原问题为 (P)，贪心选择某个局部最优项 (x) 后，原问题规约为一个子问题 (P’)。
如果 (x) 加上 (P’) 的最优解就是 (P) 的最优解，则称该问题具有贪心选择性质。
关键在于：我们无需考虑除 (x) 以外的任何选择，也无需知道 (x) 是如何影响子问题的——它一旦被选中，就永远属于最优解。

贪心选择的“无后效性”：贪心选择一旦做出，之后的过程就完全“忘记”这个选择，只关心剩下的子问题。这也就是为什么贪心算法“绝不回头看”——它不是不想回头，而是性质保证了不需要回头。

2. 为什么贪心选择性质如此重要？

它是贪心算法正确性的基石。如果不具备该性质，贪心策略可能给出错误答案（比如在 0-1 背包问题中按单位价值贪心会失败）。

同时，贪心选择性质与最优子结构一起，构成了使用贪心算法的两个必要条件：

最优子结构：问题的最优解包含其子问题的最优解。
贪心选择性质：全局最优解可以通过局部最优选择得到。

通常我们先证明贪心选择性质，再证明最优子结构（虽然有时最优子结构更显而易见）。

3. 如何证明贪心选择性质？

最常用的方法是**“交换论证法”（Exchange Argument）**，其一般步骤为：

假设存在某个全局最优解 (OPT)。
如果 (OPT) 已经包含我们做出的贪心选择，则性质直接成立。
如果 (OPT) 不包含该贪心选择，我们就修改 (OPT)：用贪心选择去替换 (OPT) 中的某个成分，得到一个新解 (OPT’)。
证明 (OPT’) 仍然是可行解，且不会比 (OPT) 差（价值不减少、长度不增加等）。
因此，包含贪心选择的解 (OPT’) 也是最优解，贪心选择性质得证。

这个过程说明：贪心选择总是可以“挤进”某个最优解中，且不会破坏最优性。

4. 经典案例：活动选择问题

问题：给定 (n) 个活动，每个活动有开始时间 (s_i) 和结束时间 (f_i)，同一时间只能参加一个活动，求最多能参加多少个活动？

贪心策略：每次都选结束时间最早的活动，然后排除与该活动冲突的其他活动，重复此过程。

证明贪心选择性质（使用交换论证）：

设活动按结束时间递增排序：(f_1 \le f_2 \le \cdots \le f_n)。
贪心选择是活动 (1)（最早结束的活动）。
设 (S) 是原问题的一个最优解集合，其活动也按结束时间排序。若 (S) 的第一个活动是 (1)，则性质得证。
若 (S) 的第一个活动是 (k)（(k \ne 1)），则由于 (f_1 \le f_k)，我们可以用活动 (1) 替换 (k)，得到新集合 (S’ = (S \setminus {k}) \cup {1})。
因为 (f_1 \le f_k)，活动 (1) 比活动 (k) 结束得更早（或同时），因此不会与 (S) 中后续活动冲突，(S’) 仍是可行解。
(S’) 的活动数量与 (S) 相等，所以也是最优解，且包含了贪心选择 (1)。

至此，证明完任何最优解都可以通过替换变成包含贪心选择的最优解，贪心选择性质成立。之后只需要对剩下的相容子问题递归应用此贪心选择即可。

5. 与动态规划的决策方式对比

回顾你之前问过的“贪心与动态规划的核心区别”，贪心选择性质正是二者分道扬镳的根源：

对比维度	贪心算法	动态规划
决策方式	每次只做一个局部最优选择，然后进入一个子问题	考虑所有可能的选择，比较它们对应的子问题最优解，再决定当前最优选择
依赖的子问题	只需求解一个子问题（例如选了活动1后，剩下的活动集）	通常需求解多个子问题（例如选不选第 (i) 件物品，需要 (dp[i-1][w]) 和 (dp[i-1][w-w_i]) 两个子问题）
是否需要“回头看”	否。选择固定，绝不修正	是。通过记录每个状态的解，实际上综合了历史信息，可以看作在多种可能中反复权衡
贪心选择性质的意义	保证那“唯一”的子问题路径就是全局最优	不适用（或不存在贪心选择性质），必须枚举所有可能才能得到全局最优

例子：在找零钱问题中，硬币面值 {1,5,11} 凑 15：

贪心（每次选最大不超过余额的硬币）不满足贪心选择性质 → 错误。
动态规划需要计算 dp[14]、dp[10]、dp[4] 等多个子问题，比较后得出最优。

6. 反例：贪心选择性质不成立的问题

0-1 背包问题：物品重量和价值不同，背包容量有限，每件物品只能选一次。

贪心策略：按单位价值排序，优先拿单位价值高的。
为什么贪心选择性质不成立？因为选了单位价值高的物品，可能占用了容量，导致后面无法放入某些组合价值更高的物品。局部最优无法保证全局最优。
用交换论证尝试证明会失败：假设最优解不包含贪心选择的物品，试图用贪心物品替换它，但贪心物品可能太重，替换后破坏了容量约束，无法得到可行解。所以交换论证走不通，贪心选择性质不成立。

这恰恰说明，贪心算法不是万能的，只有具备贪心选择性质的问题才能放心地“不回头看”。

7. 总结

定义：全局最优解可以通过一系列局部最优选择构造出来。
证明武器：交换论证法（任意最优解都可转化为包含贪心选择的最优解）。
算法设计启示：面对一个优化问题，可以先尝试贪心，然后用交换论证检验其正确性；若无法证明，则往往需要动态规划或回溯搜索。
本质：贪心选择性质为算法决策赋予了 “无后悔性”——我们可以坚定地走一条路，因为数学上已担保这条路通向全局最优。

理解了贪心选择性质，你就真正懂得了为什么贪心算法可以那么“莽撞”却又那么高效。

重叠子问题 & 最优子结构

在动态规划（Dynamic Programming）中，最优子结构和重叠子问题是判定一个问题能否用动态规划高效求解的两个核心性质，缺一不可。它们共同构成了动态规划的数学基础，也解释了为什么动态规划能够“以空间换时间”，把指数级的朴素递归降为多项式时间。

下面分别详细解释这两个性质，并结合经典实例说明它们的意义。

一、最优子结构（Optimal Substructure）

1. 定义

最优子结构是指：

一个问题的整体最优解，必然由它的若干子问题的最优解组合而成。换句话说，若要得到原问题的最优解，就必须先（或以某种顺序）求得相关子问题的最优解。

更形式化：设原问题为 (P)，其最优解为 (S)。(P) 可分解为若干子问题 (P_1, P_2, \ldots, P_k)，那么 (S) 中对应于子问题 (P_i) 的那部分解 (S_i)，一定也是子问题 (P_i) 的最优解。

2. 为什么需要最优子结构？

它是动态规划能“分而治之”的前提。如果原问题的最优解不需要依赖于子问题的最优解，那我们就无法通过求解小问题来构建大问题的答案，自底向上的递推就失去了依据。

3. 经典实例

✅ 满足最优子结构：最短路径问题

问题：求图中顶点 (u) 到 (v) 的最短路径。
最优子结构：如果 (u \rightarrow w \rightarrow v) 是 (u) 到 (v) 的一条最短路径，那么 (u \rightarrow w) 一定是 (u) 到 (w) 的最短路径，(w \rightarrow v) 也一定是 (w) 到 (v) 的最短路径。
证明（反证）：假设 (u \rightarrow w) 不是最短的，存在更短的路径 (u \rightarrow w)，那么用它替换原路径中的该段，就能得到一条更短的 (u \rightarrow v) 路径，与原路径为最短矛盾。

❌ 不满足最优子结构：最长简单路径问题

问题：求图中两个顶点之间的最长简单路径（无重复顶点）。
反例：考虑一个图，顶点 (A, B, C, D)，边 (A-B, B-C, C-D, A-D, B-D)。最长简单路径 (A \rightarrow C) 可能是 (A-D-B-C) 吗？实际上最优子结构可能不成立：假设原问题的最长路径 (A \rightarrow C) 是 (A-B-C)，但它不包含子问题 (A \rightarrow B) 的最长路径（(A \rightarrow B) 最长可能是 (A-D-C-B)，但用上这个会导致重复顶点 (C)，违反简单路径约束）。因此子问题的最优解组合后可能得不到原问题的可行解，更不用说最优解。

4. 如何识别？

证明一个问题的子结构不是最优的，通常只需举出一个反例即可；证明它具有最优子结构，一般用反证法或剪切-粘贴法：假设子问题解不是最优，就能“剪切”掉它并“粘贴”更优的子问题解，从而改进原问题的解，产生矛盾。

二、重叠子问题（Overlapping Subproblems）

1. 定义

重叠子问题是指：

在递归求解原问题的过程中，同一个子问题会被反复求解多次，而不是每次遇到都是全新的、独立的子问题。

也就是说，问题的递归树中存在大量相同的子树，这些子问题的解若被重复计算，将导致指数级的时间膨胀。

2. 为什么需要重叠子问题？

如果子问题彼此独立，从不重叠，那就是分治算法（如归并排序、快速排序）的典型特征——虽然也有最优子结构，但每个子问题只求解一次，不需要存储历史结果。动态规划的优势恰恰体现在通过记忆化（Memoization）或自底向上填表（Tabulation）来避免重复计算，将时间复杂性从指数级降到多项式级。

3. 经典实例

斐波那契数列

递归式：(F(n) = F(n-1) + F(n-2))

计算 (F(5)) 的递归树中，(F(3)) 计算了 2 次，(F(2)) 计算了 3 次，(F(1)) 计算了 5 次……大量重复。
使用动态规划，只需一个数组顺序计算，每个子问题计算一次，时间从 (O(2^n)) 降为 (O(n))。

钢条切割问题

长度为 (n) 的钢条，切割方案的最优收益依赖于不同长度子段的收益，递归过程中相同长度段的最优收益会被多次查询，若不记录就会重复计算。

0-1 背包问题

状态 dp[i][w] 可能由 dp[i-1][w] 和 dp[i-1][w-w_i] 得来，这两个子问题在求解其他 i 时又会遇到，大量重叠。

4. 与分治算法的区别

特性	分治算法（如归并排序）	动态规划
子问题关系	不重叠，每个子问题都是全新的	高度重叠，同个子问题多次出现
求解方式	递归，每个子问题独立计算	利用记忆化或递推，共享子问题解
最优子结构	通常具备，但无需“最优”组合	必须具备，且子问题解需要是“最优”的

三、两者在动态规划中的作用关系

最优子结构提供了递推关系（状态转移方程）的理论保证：我们可以用子问题的最优解来定义原问题的最优解。
重叠子问题提供了优化动机：如果每个子问题只需求解一次并存储下来，后续遇到可以直接查表，从而大幅降低时间复杂度。

动态规划的经典套路：

分析问题是否具有最优子结构，找出状态定义和状态转移方程。
发现递归过程中存在大量重叠子问题，于是决定采用备忘录递归（自顶向下）或自底向上填表来消除重复计算。
最终得到多项式时间算法。

注意：一个问题可能同时具有最优子结构和重叠子问题，但最优子结构是能用 DP 的必要条件，而重叠子问题是 DP 相比于朴素递归真正“高效”的充分条件。若没有重叠子问题，DP 的复杂度与分治相同，并无特别优势（例如二叉树的最优二叉搜索树问题，虽有最优子结构，但子问题很少重叠，DP 仍然多项式，因为状态空间就那么多，只是没有重叠也能用 DP）。

四、综合实例：0-1 背包问题（再次展示）

有 (n) 件物品，重量 (w_i)，价值 (v_i)，背包容量 (W)，每件物品只能选一次，求最大价值。

最优子结构：定义 (dp[i][c]) 为前 (i) 件物品在容量 (c) 下的最大价值。
对于第 (i) 件物品，我们有两种选择：
- 不选：(dp[i][c] = dp[i-1][c])
- 选（若可行）：(dp[i][c] = v_i + dp[i-1][c-w_i])
  最终 (dp[i][c] = \max(\text{不选}, \text{选}))。
  这里原问题的最优解直接依赖于子问题 (dp[i-1][c]) 和 (dp[i-1][c-w_i]) 的最优解，满足最优子结构。
重叠子问题：在计算过程中，对于固定的 (c)，(dp[i-1][c]) 会在多个不同的 (i) 和容量组合中被反复引用。如果使用纯递归，每个状态只计算一次会引出大量重复分支；用二维表格自底向上填表，每个状态只计算一次，时间 (O(nW))。

五、与贪心选择性质的关联

在前一问中，我们详细探讨了贪心选择性质。这里强调一下区别：

贪心算法也要求问题具有最优子结构，但它还额外要求贪心选择性质：局部最优选择直接导向全局最优，不需要再“回头”比较多个子问题。
动态规划仍然需要最优子结构，但它不依赖贪心选择性质，而是通过遍历所有可能的选择，比较各个子问题的最优解，综合得出全局最优。这也就是为什么动态规划要“回头看”之前保存的子问题解，因为它没有贪心那种“只看眼前”的底气。

可以说：

最优子结构是贪心和动态规划的共同前提；而是否具备贪心选择性质，决定了能否用贪心；若不满足，则可能需要动态规划（若同时满足重叠子问题）。

六、总结

性质	最优子结构	重叠子问题
核心要义	整体最优依赖于局部最优	子问题被反复求解
作用	确定递推关系（状态转移方程）	提供优化空间（用空间换时间）
识别方法	反证法/剪切粘贴法	画递归树，看是否有相同子问题
典型反例	最长简单路径	分治算法（如归并）没有重叠子问题
DP中的角色	必要条件	充分条件（使 DP 高效）

理解透彻这两个性质，就能准确地判断一个问题是否适合用动态规划，以及为什么动态规划能如此巧妙地化繁为简。

红黑树

1. 定义与基本性质

2. 红黑树的节点与结构

3. 旋转操作

4. 插入操作

5. 删除操作

6. 复杂度分析与比较

7. 常见应用

8. 总结

同构二叉树

递归定义（判断标准）

举例说明

与“相同/相等”二叉树的区别

常见应用

堆

准备知识：堆的数组表示

方法一：逐个插入法（自顶向下构建）

步骤

伪代码（最大堆）

时间复杂度

适用场景

方法二：从数组建堆（自底向上堆化，Floyd 建堆法）

步骤

伪代码（最大堆）

为什么正确？

时间复杂度：O(n)

适用场景

两种方法的对比

总结

哈夫曼树

1. 核心概念

2. 构造算法（贪心策略）

步骤

实例演示

3. 哈夫曼编码（前缀编码）

4. 算法正确性证明思路

5. 哈夫曼树的基本性质

6. 复杂度分析

7. 扩展：m 叉哈夫曼树

8. 应用场景

9. 总结

树

1. 直观理解：像“不断分叉的连线”

2. 严谨证明：归纳法或“剥叶子”

3. 在常见树结构中的应用

KMP

1. 暴力匹配（Brute-Force）的痛点

2. KMP 的核心：部分匹配表（next 数组）

3. 构建 next 数组（递推法）

4. KMP 匹配过程

5. 举例演示

6. 时间复杂度分析

7. next 数组的优化（KMP 的改进）

8. 应用与扩展

BM

1. 核心思想：从右向左 + 双重跳跃

2. 坏字符规则（Bad Character Rule）

3. 好后缀规则（Good Suffix Rule）

4. 完整匹配流程

5. 实例演示

6. 复杂度分析

7. 常见变体与应用

8. 总结

Sunday

1. 核心思想

2. 预处理：构建偏移表 shift

3. 匹配过程

4. 实例演示

5. 复杂度分析

6. 与 Horspool、Boyer-Moore 的区别

7. 实际应用与变种

8. 总结

选择排序

1. 核心思想

2. 算法步骤（升序为例）

3. 代码实现

Python

C++

4. 复杂度分析

5. 稳定性

2. 预处理：构建偏移表 `shift`