字符串高级主题（Sedgewick 4e）

• BFS 建立最短增广路分层图（dist 数组）
• DFS 在分层图上阻塞匹配（每次只走 dist+1 的边）
• 匹配数增长与增广路长度增长的相互制约

Hopcroft-Karp（HK）用 BFS 从所有未匹配的左侧点出发，在“仅匹配边/非匹配边交替”的图上计算每个点的最短距离分层 dist，得到当前最短增广路的长度。随后用 DFS 只沿 dist 递增的边寻找多条不相交的增广路并一次性增广（阻塞流思想），这一阶段复杂度 O(E)。每轮增广后最短增广路长度至少增加 1，而第 √V 轮之后增广路长度已经超过 √V，此时每轮至少新匹配 √V 条边，因此后段最多 √V 轮。总轮数 O(√V)，每轮 O(E)，故总复杂度 O(E√V)。

关键在于把匹配问题看成单位带宽网络上的最大流，并用“分层-阻塞”的增广路批量处理。前半段靠每轮长度增加的上界（轮数 ≤ √V），后半段靠每轮匹配数收益的下界（每轮 ≥ √V 条），两者在 √V 处平衡，从而得到 O(E√V)。

• dfn（发现时间戳）与 low（子树中可达的最小时间戳）的更新
• 系统栈（存当前未出栈的节点）的维护
• 回溯时 low[v] 的传播与缩点判定（dfn[u]==low[u]）

Tarjan 对每个节点维护 dfn[v]（首次发现时刻）和 low[v]（从 v 子树能经树边、回边、横叉边到达的仍在栈中的最小 dfn）。DFS 进入 v 时入栈并记录 dfn；对每条出边，若 w 未访问则递归并回溯时 low[v]=min(low[v],low[w])；若 w 已在栈中则 low[v]=min(low[v],dfn[w])。当 dfs 返回时若 dfn[v]==low[v]，则 v 是所在 SCC 的根，从栈顶弹出直到 v 即为一个强连通分量。整个过程只做一次 DFS，每个节点入栈出栈各一次，因此 O(V+E)。

dfn==low 说明子树内没有回边能到达 v 更早的祖先，v 之下的节点全部封闭在一个 SCC 内。栈保证只把“仍在同一可互达环”内的点归并，回边/横叉边都通过栈内判断避免误合并。

• SA 的含义（所有后缀按字典序排序后的位置）
• 最长重复子串 = LCP 数组（height）的最大值
• 模式匹配用二分查找 SA 区间，复杂度 O(|P| log n)

后缀数组 SA[i] 是第 i 小的后缀在原串中的起始位置，配合 LCP 数组 height[i]=LCP(SA[i-1],SA[i])，最长重复子串就是 height 的最大值（出现至少两次的最长公共前缀）。模式匹配 P 时，利用 SA 的字典序在 SA 上二分，找出所有以 P 为前缀的后缀区间，比较次数 O(log n)、每次比较 O(|P|)，故匹配复杂度 O(|P| log n)。构造算法有 O(n log n) 的倍增/排序法，以及 O(n) 的 DC3（Skew）与 SA-IS；后缀树可在 O(n) 内构造（如 Ukkonen），等价于 SA 加 LCP 数组。

后缀树中每个内部节点的“路径标签”对应一个重复子串，叶子的 LCP 最大值即最长重复子串。SA 是一种紧凑、内存友好的后缀树替代（加上 height 数组即可充当 LCP 信息），工程上更可取。

• LSD 从头（最低位）起的每次排序必须稳定，保证高位优先级
• MSD 从最高位递归切分桶，递归深度与字符串长度/重复前缀相关
• 内存与子问题（桶）的分配

LSD 从最低有效位开始，对每个字符键做稳定计数排序；稳定性的作用是把上一次（低位）的顺序保留到高位的排序中，从而保证最终字典序。MSD 从最高位开始，把首字符相同的串分到同一桶，再对每个桶递归处理下一字符。其递归深度最坏达到字符串长度 L（如所有串共享同一长前缀），子串长度小于某个阈值时改为插入排序以免递归过深；内存上每层需按桶分配计数数组和辅助数组，可复用计数数组避免重复分配。

LSD 的方便处在于无需递归、处理变长串时把短串视为已补齐；但需要遍历全部字符，对短串多的场景不划算。MSD 对短串高效、分摊只处理共享前缀，但递归深度与重复前缀成正比，须用阈值切换和子数组索引传递（而非物理拷贝）控制内存。

• height 数组（相邻后缀 LCP）的定义
• 最长重复子串 = max height
• 不同子串计数 = n(n+1)/2 − Σ height

设 SA、height[i]=LCP(SA[i-1],SA[i])。最长重复子串 = max_i height[i]（出现 ≥2 次的最长公共前缀）。本质不同子串数 = 所有后缀子串总数减去相邻后缀重复的前缀：Σ_i (n−SA[i]+1) − Σ_i height[i] = n(n+1)/2 − Σ height。模式 P 的出现次数 = 以 P 为前缀的后缀区间长度，通过对 SA 做两次二分（最后/第一个 ≥P 的位置）得到区间 [l,r]，次数 = r−l+1，配合 height 的 RMQ 可快速比较，查询 O(|P| log n) 或 O(|P|+log n)。

相邻后缀的 LCP 恰好覆盖了“多计”的重复前缀，height 序列的“分割”作用让上述统计都能在 SA 的单调结构上线性完成。这类问题集中体现了“SA+height 即后缀树的紧凑表示”这一核心思想。

• BWT 把文本重排后形成局部性（相同字符聚集）
• LF-mapping 与排序后缀数组的关系
• run-length 编码利用 L 列的长游程

BWT 把原串的所有循环移位按字典序排序，取最后一列 L 作为变换结果。由于带相同上下文（相同后续字符）的字符在排序后相邻，L 列中相同字符往往聚成长游程，便于 run-length 编码（以及 MTF+熵编码）大幅压缩。LF-mapping 记录了 L 列第 i 个字符在 F 列（排序后第一列）应映射到的位置，利用 F 列与 L 列之间的“第 k 个字符相等”关系，可在 O(1) 内实现 backward search，即从后往前匹配模式。排序后缀数组的过程正是把循环移位排序，为 LF-mapping 提供了严格的双射结构。

压缩率提高来自 BWT 的“上下文聚类”效应：具有相同后缀的字符被排到相邻位置，使游程变长；同时 BWT 是可逆的（通过 LF-mapping 从 L 列恢复原串），因此既压缩又无损。这也正是 FM-Index 与生物信息学压缩的基础。

• Ford-Fulkerson 任意增广路、Edmonds-Karp 用 BFS 最短增广路
• Dinic 的 BFS 分层 + DFS 阻塞流
• SAP 的模拟标号与 GAP 启发式（层无标号即终止）

Ford-Fulkerson 用 DFS 找任意容量增广路，可能因整数但路径长度反复而慢；Edmonds-Karp 用 BFS 每次找最短增广路，复杂度 O(VE²)。Dinic 每轮先用 BFS 按残留容量求分层图（每点距离标号），再用 DFS 只沿标号递增的边找阻塞流（一次 DFS 可增广多条路径，配合当前弧优化），复杂度 O(V²E)，单位容量图 O(E√V)。SAP（Shortest Augmenting Path）是“模拟的”标号法，直接用 BFS 逐点找最短增广路，避免显式分层。GAP 优化在 SAP 中维护各距离标号的节点计数，当某层标号缺失（出现 gap）时，说明该层之上的点无法再汇入汇点，直接终止，显著加速。

核心是用“最短路径 + 阻塞流”思想控制增广路数量。Dinic 的 BFS 分层 + DFS 阻塞（含当前弧）把每轮费用限制在 O(E)，GAP 则进一步在层数断档时提前收敛，两者都是工程上常用的加速手段。

• Kosaraju：正图 DFS 记录完成序，反图 DFS 按序收缩
• Gabow：单次 DFS + 辅助栈，无递归嵌套正反图
• 常数因子与栈深对比

Kosaraju 需要两遍 DFS：先在原图记每个节点的完成时间，再在反图上按完成时间降序 DFS，每次 DFS 的一套连通点即一个 SCC。它实现简单、正确性直观，但需要存储反图和两次遍历，常数因子较大。Gabow 与 Tarjan 类似，单次 DFS 用两个栈（主栈存当前路径、辅助栈存 SCC 编号候选）在线性时间内求 SCC，无需反图，栈深与递归深度有关，常数因子更小。时间上两者都是 O(V+E)，但 Gabow 常数更好、内存更省（不建反图）。

Kosaraju 的“反图 + 完成序”思想漂亮但工程代价高（两遍 DFS + 反图）。Gabow 用路径栈替代 low 值，避免了 Tarjan 中需要同时维护 dfn/low 的额外变量，常数更小。选择取决于是否在意常数与内存。

• 大规模数据下内存布局与缓存友好性
• CSR 邻接表的紧凑存储
• 避免动态分配与指针开销

在 10^6 节点、10^7 边的规模下，图必须用紧凑的内存布局存储。CSR（压缩稀疏行）用两个数组（offset 与 adj）顺序存储邻接边，避免指针和链表节点开销，内存仅为 O(V+E) 且缓存友好。ELS（Edge List）把边顺序存储，配合静态数组便于 BFS/DFS 顺序扫描。HK 的 BFS 与 DFS 需要高频随机访问邻接表，用预分配的静态数组+CSR 能减少 cache miss 与动态分配开销，保证 O(E√V) 的实际常数很小。

大规模图算法的瓶颈往往不是渐近复杂度而是内存局部性。CSR 把整行邻接连续存放，配合预分配、无动态 new 的静态数组，能显著降低 TLB 与缓存缺失，是 10^6 以上规模的标准工程做法。

• Z[i] 表示 i 处后缀与整串的最长公共前缀
• π[i] 表示前缀的最长真 border 长度
• 两者可互相推导（O(n) 转换）

Z[i] 是 s 与 s[i:] 的 LCP；π[i] 是 s[0..i] 的最长真 border（真前后缀）长度。两者等价：Z 数组的“扩展”关系可用来累积出 π，具体做法是 Z-box 内每个位置继承前一个位置的 π 值；反过来 π 数组也能通过“反向匹配”计算 Z。实际转换：由 Z 到 π，对每个 i>0 若 Z[i]>0 则更新 π[i+Z[i]-1] = max(π[i+Z[i]-1], Z[i])，再倒序做 π[i]=max(π[i],π[i+1]) 的传递；由 π 到 Z 则可借助 border 链匹配。边界下标相差 1（π 以 i 为右端，Z 以 i 为左端），转换时需注意 ±1 偏移。

Z 与 π 提供两种等价的分治视角：Z 从“头部 LCP”出发，π 从“末尾 border”出发。两者在 O(n) 内可互转，工程上按题目便于观察的方向选择即可。

• Kasai O(n) 构造 height 数组
• 相邻后缀 LCP 的 RMQ 区间（各后缀对 LCP 为区间最小）
• Phi/PLCP 数组逆序计算 LCP

Kasai 算法用“LCP(SA[i],SA[i+1]) ≥ LCP(SA[i-1],SA[i]) − 1”的性质，在线性时间内从 SA 构造 height 数组。对任意两个后缀，其 LCP 等于它们之间所有相邻 height 的最小值，即区间 RMQ，因此可用稀疏表等 O(1) 查询。最长公共子串（两个串）可把两串拼接后求 SA，跨串的后缀中 height 的最大值即答案。Phi/PLCP 数组是 Kasai 的等价变体：先按“ph[i]=SA 中 i 前一位置”记录后缀顺序，再逆序计算 LCP 值，省去中间数组，同样 O(n)。

核心是“height 序列的区间最小值 = 任意两后缀 LCP”这一 RMQ 等价关系，把 LCS 问题化为对 height 的扫描/RMQ。Kasai 与 Phi/PLCP 都是为实现 O(n) 构造 height 的工程手段。

• 中心扩展 + 对称性复用（回文臂）
• 奇偶回文用统一半径数组（d1/d2）或填充字符
• 与 O(n²) DP、O(n log n) 或 O(n) 哈希二分对比

Manacher 维护一个“当前最右回文右端点 R 及其中心 C”，对每个中心 i 若在 R 内则用对称点 j=2C−i 的半径初始化，再向外扩展，保证每个位置最多被扩展一次，总 O(n)。奇回文用 d1[i]（半径，含中心，长度=2d1-1），偶回文用 d2[i]（中心在两字符间，长度=2d2），也可用间隔符 # 统一。对比：DP（区间 DP）用 O(n²) 时间与空间；滚动哈希+二分用 O(n log n) 或 O(n) 但依赖哈希碰撞概率、且需额外验证。Manacher 是确定性的 O(n)。

Manacher 的关键是把“已知回文覆盖区”的对称信息复用到新中心，避免重复扩展，这是线性上界成立的依据。相比 DP 更省、相比哈希更稳，是求最长回文子串的标准线性算法。

• 回溯式引擎（backtracking）的指数最坏情况
• NFA 模拟（Thompson/Pike）的线性保证
• 各引擎的取舍

回溯式引擎（如 PCRE、ICU、Boost regex 默认、Java/许多语言）把正则编译成模式并沿“尝试-回溯”搜索，最坏情况对形如 (a*)*b 的输入产生指数级路径（cataclysmic backtracking），易被 ReDoS 攻击。RE2 与 grep 的 GNU 实现采用 Thompson NFA 模拟：把正则编译成 NFA，用“当前活跃状态集合”按字符推进，每个字符 O(状态数)，复杂度线性、无指数爆炸，但失去捕获组/回溯引用等高级特性。ICU 与 Boost 提供不同模式，ICU 默认回溯但可设置；Boost 也有 regex 编译选项。选择核心是：需要捕获组/反向引用则用回溯引擎，需要抗 DoS 与线性保证则用 NFA 模拟。

指数爆炸源于回溯引擎的“每步尝试后再回溯”在多个量词叠加时呈指数搜索空间。NFA 模拟本质是“并行地跟踪所有可能路径”，把路径爆炸压缩为状态集合的大小，从而保证线性。

• failure 边指向“最长真后缀”所在节点
• BFS 保证父节点先于子节点处理
• DFS 可能导致 violation 处理顺序错误

AC 自动机的 failure 边要求节点 u 的 failure 指向“u 代表串的最长真后缀”对应的节点，而该后缀节点在 BFS 中一定先于 u 被访问（BFS 按深度分层，父节点深度 < 子节点深度）。因此从父节点 failure 出发沿 failure 链匹配即可 O(1) 求出子节点 failure，构造总复杂度 O(总字符数)。若用 DFS，由于子节点可能先于其“后缀节点”被访问，无法保证 O(1) 递推，可能需回溯或反复查链，复杂度退化。

BFS 的“按深度分层”性质恰好与 failure 的定义（指向更短后缀）一致，使得每个节点的 failure 由父链上已确定的节点推出，这是 AC 构造线性、正确的原因。

• 子句 (x∨y) 蕴含两条边：¬x→y, ¬y→x
• 一变量与其否定在同一 SCC 则不可满足
• 按拓扑序反向赋值

对每个布尔变量 x 建两个顶点 x 与 ¬x。子句 (x∨y) 等价于两条蕴含边 ¬x→y 与 ¬y→x。若存在 x 与 ¬x 在同一 SCC，则无解；否则按 SCC 的拓扑序，对每个 SCC 取“先出现的 SCC 中变量值”即可构造一组满足赋值（具体地，在缩点后的 DAG 上按拓扑逆序赋值，先被赋值的可为真）。整体 O(V+E)。拓扑关系保证不会出现“赋值 x 为真却蕴含 ¬x 为真”的矛盾。

蕴含图把 2-SAT 变成“命题逻辑可达性”问题：x 能为真当且仅当不存在 ¬x→x 的路径迫使 x 为假。SCC 判定矛盾、拓扑序赋值是线性时间的关键。

• BWT 的 LF-mapping 与 backward search
• occurrence（计数）数组与 checkpoint 的稀疏化
• bitvector 的 rank/select 支持 O(1) 或 O(log) 查询

FM-Index 用 BWT 的 L 列与 LF-mapping 实现 backward search：从模式 P 的最后一个字符开始，逐步用 LF 函数把匹配区间 [l,r] 扩大成“前缀匹配 P 的后缀”的 SA 区间，最终区间大小即 P 的出现次数。为高效实现 LF 中的 rank 操作（统计某字符在 L[0..i] 中出现次数），用 occurrence 数组配合 checkpoint 稀疏存储：每隔若干位置存全量计数，块内用 bitvector 的 rank/select 累加，从而 O(log Σ) 或 O(1) 完成。整体查询 O(|P|·rank时间)，无需解压全文。

FM-Index 把 BWT 的压缩性（小空间）与后缀数组的检索能力（子串定位）结合，backward search 通过 LF 在 O(|P|) 次迭代内完成，rank/select 与 checkpoint 是空间-时间折中的关键。

• 可行标号 l(x)+l(y) ≥ w(x,y)
• 相等子图（含标号相等边）中的完全匹配即最优匹配
• 交替树扩展与标号调整保持不变量

KM 算法为左右顶点维护可行标号使 l(x)+l(y) ≥ w(x,y)，并只考虑“相等边”（l(x)+l(y)=w(x,y)）构成的相等子图。若在某次匹配中相等子图含完美匹配，则它一定是最大权匹配（因为任意匹配权 ≤ Σ l(x)+l(y)，而相等子图完全匹配权 = Σ l(x)+l(y)）。当找不到完全匹配时，用交替树（当前匹配的交替路径）计算松弛量 δ = min 的标号差，调整标号使相等子图扩大，重复至完全匹配。每次调整至少增加一条相等边，总调整 O(n) 次，每轮 O(n²)，故 O(n³)。

关键是“相等子图完全匹配 ⇔ 最优”这一对偶不变量，标号调整是原始-对偶方法（类似匈牙利/网络流的松弛）的体现，保证每次迭代都严格朝可行方向推进。

• Trie 的 children 数组（每节点 R 个指针）在大字符集下内存大
• TST 每节点 3 个指针（小于/等于/大于），以比较换空间
• 查找性能对比

标准 Trie 每个节点存 R 个指针（R 为字符集大小），字符集大（如 Unicode 6 万字符）时内存爆炸。Ternary Search Trie 每节点只有 3 个指针（左子、中子孙、右子）和 1 个字符，按字符比较决定走左/中/右，以 O(字符数) 的查找比较换 O(1) 的指针数组存储，空间 O(n·字符数) 但常数小得多。查找 TST 平均 O(log n) 或 O(字符数×log)，最坏 O(字符数) 比较；Trie 查找 O(字符数) 但每字符 O(1)。TST 适合字符集大、内存受限的场景，Trie 适合字符集小、查找最频繁的场景。

这是“数组指针 vs 比较树”的经典权衡：Trie 用空间换时间，TST 用时间换空间并把 R 叉存储压成 3 叉。大字符集下 TST 的缓存与内存优势明显。

• 滚动哈希值 = 多项式模一个质数
• 碰撞概率 ~ 串长度/模数
• 多用几个不同模数/基的哈希防御

Rabin-Karp 把串编码为多项式哈希 h = (s[0]·B^k + ...) mod M，滑动窗口时用 O(1) 更新（去头、移倍、加尾），B 为基数、M 为模。碰撞发生在两个不同串哈希值相等时，概率约为 O(k/M) 或残差串数/M，单模 M~2^61 时对单次比较碰撞概率可忽略，但多窗口、多模式时会放大。防御手段：用多个独立模数（如双 64 位模或 2^61-1 与 2^64-1 组合）相乘把碰撞概率压到可忽略；或对候选命中做逐字符确认（校验）。无碰撞时复杂度 O(n+m)，最坏 O(n·m)。

碰撞概率随模数倒数和串长度线性增长，多哈希把“单哈希碰巧相等”的偶然事件变成“多哈希同时碰巧相等”的极小事件，实测可当作确定性使用。

• 生日悖论：碰撞概率 ~ n²/2/2^w
• 64 位哈希在 10^9 输入下概率 ~ 10^18/2^64 ≈ 0.05
• 双哈希乘积把概率降到 ~ (n²/2/2^w)²

生日悖论给出 n 个值在 2^w 空间中的碰撞概率约 n²/(2·2^w)。对 64 位哈希（w=64），n=10^9 时概率 ≈ 10^18/(2·1.8×10^19) ≈ 0.03–0.05，不可忽略。双哈希用两个独立 64 位哈希（或 128 位组合）要求两者同时相等才算碰撞，概率约为单哈希碰撞概率的平方（≈(0.05)²≈0.0025，若用 128 位则更小到可忽略）。因此双哈希/O(1)多重校验把碰撞概率压到实际可忽略。

生日悖论说明碰撞概率随输入量的平方增长，仅靠增大位宽到 64 位在 10^9 量级仍不够；双哈希把“两个独立哈希同时碰撞”概率相乘，等价于把有效位宽翻倍，是工程上可靠的防御。

• Thompson 构造：正则 → ε-NFA，O(|re|) 状态
• 子集构造：ε-NFA → DFA，状态数可能指数爆炸
• 工程上对 DFA 状态数做切分/压缩

Thompson 构造把正则递归编译成 ε-NFA，状态数 O(|re|)、无指数问题。子集构造（subset construction）把 NFA 的 ε-闭包集合作为 DFA 状态，最坏情况下 DFA 状态数可达 2^|Q|（指数），当正则含大量并置/星号时（如 (a|b)*a(a|b)^k）会爆炸。因此当 |re| 或派生 DFA 状态阈值过大时，工程上采用：不构建 DFA 而直接 NFA 模拟（RE2 方式）、对 DFA 做最小化（合并等价状态）、或对模式分段/限制长度。经验阈值：状态数超过几万~几十万即应切分或切换为 NFA 模拟。

关键取舍是“NFA 模拟的时间 vs 构建 DFA 的空间”。NFA 模拟每字符 O(状态数) 稳定，DFA 每字符 O(1) 但构建可能指数；需要按模式规模与可用内存动态选择。

• 流式数据的窗口滑动与哈希快速更新
• 动态字典（增删模式）的哈希比较
• 候选集减少较验次数

在流式场景中，文本以流形式到达，需要固定滑动窗口持续匹配；滚动哈希允许窗口移动时 O(1) 更新窗口内容的哈希值，无需重算。当字典动态变化（增删模式）时，用哈希表维护当前模式集合，对每个窗口哈希用候选集（与窗口哈希同桶的模式）做精确比对，避免与全部模式比较。候选集+滚动哈希把每次匹配的期望代价降到 O(1) 附近，且支持动态更新。

哈希把“比较字符串”降为“比较整数键”，滚动哈希让窗口滑动可增量更新，候选集让匹配只针对同哈希的模式。这是流式/在线匹配的标准工程组合。

• KMP 预处理 O(m)，匹配 O(n+m)
• Boyer-Moore 从右往左、坏字符/好后缀跳跃
• 英文（大字符集）与二进制（小字符集）的差异

KMP 预处理 prefix function 的 O(m) 常数为下界（需扫一遍模式），总复杂度 O(n+m)。Boyer-Moore 从模式右端向左匹配，坏字符规则在文本字符不在模式中时跳 m 位，好后缀规则利用已匹配后缀对齐；在英文（大字符集）上坏字符规则跳跃频繁，实践中常比 KMP 快 3~5 倍以上；在二进制（小字符集）上坏字符表几乎无跳跃（字符频繁出现），好发挥好后缀与预处理，但胜率下降，甚至接近朴素。总体 BM 常数好但最坏 O(nm)，KMP 最坏线性但常数大。

BM 的“从右向左+坏字符跳跃”在字符集大、文本随机时跳跃量大，故英文胜率高；二进制字符集小导致坏字符命中频繁、跳跃受限，优势减弱。KMP 最坏稳定但预处理与指针开销大。

• AC 自动机构建 O(总模式长度) 时间与内存
• 10k–10M 模式的字典规模对内存的影响
• 字符集大小（ASCII vs DNA 4 字母）影响 children 存储

AC 自动机构建时间与内存正比于模式字典总长度（节点数约等于总字符数）。10k–10M 模式对应节点数从百万到上亿级：若每节点用字符集大小的数组（256 或 4 或 26）存 children，则内存 = 节点数 × 字符集 × 指针大小，10M 模式会占数 GB~数十 GB。DNA motif（4 字符集）可用紧凑数组或哈希表，内存小得多；敏感词/IDS 用 ASCII 需更大数组。初始化需遍历所有模式建 trie + BFS 建 failure，代价 O(总长度)，10M 模式需额外内存与时间。工程上常压缩 children（哈希表/排序数组/动态向量）或分片字典。

AC 的内存瓶颈是每个节点的 children 存储。字符集小（DNA）用数组省、字符集大（Unicode）用哈希/排序数组省，模式量极大时需分片或压缩，初始化代价随总长度线性增长。

• APX 类与 APX-hard（无 PTAS 除非 P=NP）
• PTAS 复杂度随 ε 多项式依赖 n，FPTAS 还随 ε 多项式
• MAX-3SAT 的 APX-hardness、METRIC-TSP 有 3/2 近似

APX 是存在常数近似比的优化问题类；APX-hard 表示若问题有 PTAS 则 P=NP（即不存在任意 ε 的近似方案）。MAX-3SAT 是 APX-hard 的（除非 P=NP 无 PTAS），但可由随机/去随机化得到 7/8 近似。METRIC-TSP 不是 APX-hard 意义下无界，有 3/2 近似（Christofides 算法），且已知不可在 3/2−ε 内近似（除非 P=NP）。PTAS 对任意 ε 在 O(n^f(ε)) 内近似，FPTAS 进一步要求复杂度关于 1/ε 多项式（如欧几里得 TSP 有 PTAS）。落地：能否有常数近似、能否逼近到任意 ε，取决于问题的 APX-hardness 边界。

APX-hard 是“无 PTAS”的不可近似性证明工具，PTAS/FPTAS 是“可任意逼近”的算法类。MAX-3SAT 与 METRIC-TSP 分别落在 APX-hard（无 PTAS）与有常数近似但可能无 PTAS 的边界，体现近似难度分层。

• goto 表：trie 的转移边
• failure 表：最长真后缀的前缀状态
• output 表：命中模式（含 via failure）

AC 自动机由三部分构成：goto 表（trie 转移，深层的缺省转移指向 root 或与 failure 结合）、failure 表（BFS 构建，指向当前状态串的最长真后缀对应的前缀状态）、output 表（记录在哪些状态命中哪些模式，含通过 failure 链继承的命中）。匹配时从 root 出发，对文本每个字符走 goto，若某字符无 goto 则沿 failure 跳到可达状态再试；并检查 output 输出命中。增量匹配只需线性扫描文本，每字符常数操作，总 O(n + 命中数)。

failure 表使“失配时跳转”不重复扫描，output 表把“经 failure 后的 hit”一并报告，保证扫描文本时一次遍历即可找到所有模式，这是 AC 的 O(n) 保证。

• B 树原地更新，随机写需多次 I/O
• LSM 顺序写 + 内存缓冲 + 压缩合并
• 读路径：B 树 O(log n) 单次读，LSM 需检查多层

B 树把数据原地组织在磁盘页中，随机写会导致多次页擦写与 I/O 放大，但读路径单次 O(log n) 查找、点查快；LSM 把写追加到内存缓冲（memtable），flush 成有序 SSTable 文件，靠后台压缩（compaction）合并，随机写被转成顺序写、写放大可控但读路径需检查多层 SSTable（可用布隆过滤器/Bloom 加速）。LSM 适合写密集、append-heavy 负载（如日志、监控、时序）；B 树适合读密集、需要稳定点查/范围查询的负载（如传统 OLTP 数据库）。牺牲了读的 LSM 用压缩换写吞吐。

核心是“写路径 vs 读路径”的权衡：B 树用原地更新换读快，LSM 用顺序写+压缩换写快、代价是读放大与压缩停顿。OLTP 选型取决于读/写比与延迟要求。

• B 树阶（每节点最大键数）决定树高与页大小
• 分裂/合并触发页写
• 延迟合并减少写放大

B 树的阶（每个节点最多键数）决定每个磁盘页能容纳的键数，影响树高（页越大树越矮，点查 I/O 越少）和页分裂频率。插入键满时分裂节点（一个新节点 + 上层键上移），删除导致节点过空时合并（或借键）。每次分裂/合并都涉及页的写回，造成写放大。延迟合并（lazy merge）把低占用节点先标记、合并延后，减少频繁的页写。工程上通过选择合适页大小（如 4KB–16KB）、分裂阈值与延迟合并策略平衡点查 I/O 与写放大。

阶/页大小是空间与 I/O 的折中：页大则树矮、读 I/O 少但单页写代价大；分裂/合并是维护 B 树平衡的必然操作，其频率决定写放大，延迟合并可摊薄其成本。

• 当前弧优化避免重复扫描已用尽边
• 分层图压缩减少无效边
• 并行化的同步与竞争瓶颈

Dinic 的当前弧优化记录每个节点“当前已尝试到的邻接边”，避免 DFS 反复扫描已饱和的边，把每轮阻塞流降到 O(E)。分层图压缩只保留能推进层数的边（dist 递增），剪掉无用边。多核并行时，多个线程同时 push 流会竞争共享的邻接表、容量与当前弧指针，导致同步开销与 cache 竞争；还需保证增广的一致性（避免同一路径被并发修改）。常用策略是分块/分阶段并行、用原子操作或给每个节点独立锁，但瓶颈通常是共享的容量数组与当前弧指针的写竞争。

当前弧与分层是串行常数优化，并行时瓶颈转移到共享数据结构的写竞争与同步。并行加速有限，通常需按子图/分层阶段划分并行度。

• Huffman 的最优性（贪心合并最小权）
• 长度受限 Huffman（限制最大码长）
• 范式 Huffman（canonical）与 B-ary 树

Huffman 的最优性由贪心归并两个最小频率节点证明：任何其他前缀码树都能通过交换把最小权节点放得更深来改善，因此每步合并最小权得到最优树，压缩率最优（给定符号分布）。长度受限变体（如 package-merge）在限制最大码长下仍近似最优，用于约束最坏码长。范式 Huffman 只传码长序列（按码长排序的符号），解码端按序重建，节省表传输。B-ary Huffman 每步合并 B 个最小权，适合每符号需 B 位的输出或等长码场景，兼顾压缩率与块/码长对齐。

Huffman 的最优性来自“最小权归并的贪心正确性”，工程上通过范式编码省表、长度受限控码长、B-ary 对齐块大小，在压缩率与实现代价间折中。

• 反多项式等价（多项式归约）用于 NP 完全性
• 反指数等价（指数归约）用于密码学困难性
• 归约保持的“难度级别”

反多项式等价（polynomial-time reduction）把一个难题 A 归约到另一问题 B，若 B 多项式可解则 A 也可解，用于证明 A 至少和 B 一样难（NP 完全性）。反指数等价（指数时间归约）用于密码学：若存在多项式算法破解密码则能破解某已知难问题，且归约保持指数时间下界，用于建立“困难等价”的密码假设（如离散对数、整数分解）。在算法竞赛中，主要用多项式归约证明 NP 完全性以判断能否多项式求解；在密码学中，指数归约用于论证安全假设的“等难度”。

两种归约在不同时间尺度上保持“可解性”的反向蕴含：多项式归约保持多项式可解性，指数归约保持指数不可解性。应用场景决定用哪种归约作为难度论证。

• 各复杂度类定义：co-NP、PSPACE、#P、APX、FPT
• ETH 与 Strong ETH 的指数时间假设
• 类之间的包含关系

co-NP 是“否实例有短证明”的类（补问题的 NP）；PSPACE 是多项式空间可解（含 NP 与 co-NP）；#P 是计数问题（数解个数）类，比 NP 更难（含 #SAT）；APX 是带常数近似比的问题类；FPT 是固定参数可解（参数化复杂度，复杂度 O(f(k)·n^c)）。ETH 断言 3SAT 不存在 2^o(n) 算法，Strong ETH（SETH）主导的 kSAT 不能在 2^(1−ε)n 内解决，SETH 用于证明某些问题的条件性下界（如三和问题、LCS 的 n^{2−ε} 下界）。关系上 co-NP、PSPACE 是决定性问题，NP ⊆ PSPACE ⊆ EXP；#P 是计数类（推出 NP 可解）；APX 是优化类；FPT 是参数化类，与上述类正交。

这些类分别刻画“补问题、空间、计数、近似、参数化”的难度，ETH/SETH 是更强的不可解假设，用于在 P≠NP 之外给出更细的条件性下界。

• LZW 码本从初始大小线性增长
• CODE_MAX 码长上限与 clear code 重置
• GIF/TIFF 的变体差异

LZW 把字符串编码为逐步增长的码本，初始码本大小为 2^k（k 为位宽，如 8 位数据 256 个单字符码），每新增一个码字码本+1，当位宽用尽或达到 CODE_MAX 时，GIF 用 clear code 重置码本（GIF 规定明确的 clear code 码字），TIFF 无 clear code、用可变位宽。early change 指在码本即将满员时提前切换码长（GIF 变体），避免编码长度突跳。GIF 用可变位宽+clear code、TIFF 用可变位宽且无 clear code，差异在于位宽增长策略与 clear code 的保留。（注：PNG 不使用 LZW，压缩采用 zlib/Deflate。）

码本增长与位宽切换是 LZW 压缩率与格式兼容的关键。GIF 的 clear code 与 early change 让它能处理数据变化，TIFF 无 clear code 的可变位宽策略相对简单，各自为格式的简单性与压缩率权衡。

• Lipton-Tarjan：平面图有 O(√n) 分离器
• 递归切分的分治算法
• 在几何近似与图划分中的应用

Lipton-Tarjan 定理指出任意 n 顶点平面图存在 O(√n) 大小的分离器，删去后把图分成两个大小不超过 2n/3 的部分，并且分离器可线性时间找到。基于此做递归切分（分治）可把平面图问题（如平面图上的独立集、支配集，或平面图全源最短路径）递归地分解，得分 O(n^1.5) 或更优的算法；也用于几何问题（平面图嵌入的划分）与近似算法（对平面图做常数近似）。递归切分在每层把问题分成两个子问题+一个分离器规模，总复杂度由 δ(n)=O(√n) 的分离器递归驱动。

平面图分离器把“平面性”转成“可递归分割”，从而引出分治算法与近似。递归深度 O(log n)，每层总规模受分离器约束，是图划分与几何算法的基础工具。

• FIFO 队列调度
• Highest-Label 选最高标号活动点
• Wave 与全局间隙启发式

Push-Relabel 维护每个节点的“高度”与“多余流”，通过 push 与 relabel 迭代。FIFO 用队列按先进先出调度活动点，简单、适合一般网络，复杂度 O(V³)。Highest-Label 每次选择标号最高的活动点，能减少 relabel 次数，对高图（图深）效果好。Wave 按阶段扫描所有活动点，适合部署式实现。全局间隙启发式（gap heuristic）在标号出现断档时提前终止该层以上的处理，对高度分层明显的网络加速显著。选择：FIFO 通用、Highest-Label 适合潜流长的图、Wave 适合并行/批处理、gap 适合高度分层网络。

不同调度策略改变活动点处理顺序与 relabel 次数，从而影响常数。Highest-Label 与 gap 利用“高度结构”减少无效操作，是工程上常用的加速启发式。

• push 与 relabel 的基本操作
• discharge 调度活动点
• highest-label 与 gap/全局重标加速

Push-Relabel 核心操作是 push（把多余流沿许可边推进）与 relabel（抬高节点高度使可推）。discharge 调度反复对一个活动点 push 直到其无多余流或需 relabel；活动点用 FIFO 或 highest-label 管理。highest-label 只处理标号最高的活动点，减少不必要的 relabel。gap 启发式识别标号断层，把高度更高的节点直接标为不可达（跳过）；全局重标（global relabeling）周期性地用 BFS 重算高度，避免高度被反复抬高导致大量无效 relabel。这些优化显著降低 relabel 次数，是实测性能的关键。

relabel 次数是 Push-Relabel 主要的开销来源。highest-label 减少无效 relabel，gap 与全局重标直接压缩高度域，使算法在稀疏/深网络上更接近 O(V²√E) 的实用性能。

• P：多项式时间可解
• NP：多项式时间可验证
• NP-Hard：至少同 NP 一样难（可归约到它）

P 是能在多项式时间判定的问题类；NP 是解的可在多项式时间验证的问题类（未必能在多项式时间解）；NP-Hard 是“所有 NP 问题都能多项式归约到它”的问题，至少与 NP 一样难（可能不是 NP 本身，如停机问题）；NP-Complete 是既是 NP 又是 NP-Hard 的问题。关系：P ⊆ NP，NP-Complete ⊆ NP，NP-Complete ⊆ NP-Hard。共同点反例：NP-Hard 中不属于 NP 的问题（如停机问题）不是 NP-Complete；P 中是否有 NP-Complete 问题取决于 P=NP 是否成立（若 P=NP 则所有非平凡 NP 问题都是 NP-Complete）。

区分关键在于“可验证”vs“可解”vs“难度下界”。NP-Hard 不要求属于 NP，NP-Complete 要求属 NP 且 hardest；停机问题等不可判定问题揭示 NP-Hard≠NP-Complete。

• 滚动哈希与模运算
• 双哈希/确定性校验
• 多模式切分减少候选比较

Rabin-Karp 用模运算的滚动哈希在窗口滑动时 O(1) 更新，碰撞概率约正比于窗口数/模数。控制方法：用大质数模（如 2^61−1）或 2^64 自然溢出；用 double hashing（两个独立哈希）把碰撞概率降到单哈希的平方；对候选命中做逐字符确认（确定性）；多模式切分把文本/模式按块切分，缩小每个窗口的哈希比较范围，减少同哈希的候选集。综合起来把碰撞概率压到可忽略，复杂度近似 O(n+m)。

碰撞控制的核心是“降低单哈希巧合概率 + 缩小候选集 + 确定性校验”。模运算与双哈希量化概率，切分减少候选，逐字符确认消除误报，组合使用保证正确性。

• 终止符防止后缀是另一后缀的前缀
• 唯一性保证排序唯一
• 最小性保证字典序正确

在 suffix array 与 FM-Index 中，把终止符 $ 追加到串尾，要求 $ 小于所有字符（最小）且唯一（不出现于串中间）。最小性保证含 $ 的后缀（如 "$"、"ab$"）在字典序排序中排在以相同前缀结尾的普通后缀之前，使后缀比较有明确终止；唯一性保证所有后缀两两不同（不存在一个后缀是另一后缀的前缀），从而排序结果唯一、LCP 计算与模式匹配区间划分正确。若 $ 不唯一或非最小，会出现后缀相等或前缀重叠，破坏 SA 的严格排序与 LF 映射的一一性。

终止符是“后缀比较的终止标记”，最小唯一性确保后缀集是“无前缀关系”的集合，这是 SA 排序、LCP 与 FM-Index 的 LF 映射成立的先决条件。

• MST 的 2-近似
• 11/7（约 1.55）近似
• 欧几里得平面下的 PTAS

Steiner Tree 求连接所有终端的最小连通子图，可加入 Steiner 点。基于 MST 的 2-近似：对终端集合求最小生成树，其长度 ≤ 2×最优 Steiner 树（因为最优树可被欧拉环游一趟 ≤ 2，或终端 MST 长度 ≤ 最优树长度 ×2）。更优的 11/7≈1.55 近似利用“最优树中 Steiner 点度数结构”精细化。欧几里得平面（metric）下，把平面网格化、用分治/DP 组合出 PTAS（任意 ε 近似）。不可近似性：一般图 Steiner Tree 无 PTAS（除非 P=NP），是 APX-hard 的，近似比下界为常数（如 96/95 或更好）。

2-近似来自 MST 与最优树的关系（欧拉环游/双倍遍历），11/7 用更紧的树结构。欧几里得 PTAS 用网格-分治打包，一般图则因 APX-hard 无 PTAS。边界反映了几何附加结构带来的近似优势。

• 常数因子与内存对比
• 实现难度
• 各自适用场景

Suffix Array 是紧凑的整数数组，内存 O(n·4 或 8 字节)，配合 height 数组可完成后缀树能做的多数查询，但某些查询（如任意后缀 LCP、模式匹配）需额外 RMQ 或二分，常数因子略大。Suffix Tree 直接存储所有后缀的树结构，每个内部节点含子节点指针，内存 O(n) 但常数大（每节点多指针），构建（Ukkonen）实现复杂、易错。工程权衡：SA 易实现、内存小、缓存友好，适合大规模文本；Suffix Tree 查询直观（整串匹配、在线）但实现难、内存大。多数工程用 SA 作为后缀树的紧凑替代。

SA 用小内存和可接受的查询常数换实现简单，Suffix Tree 用空间换查询直观。现代工程（如压缩索引、生物信息）普遍倾向 SA+height 或更紧凑的 FM-Index。

• SA-IS 与 DC3/Skew 的线性时间构造
• 内存与常数因子
• 实现复杂度

DC3（Skew）用“取模 3 分桶 + 递归 + 合并”在 O(n) 内构造 SA，需要额外 2n 左右空间（多重数组），常数较大、实现相对复杂。SA-IS 用“诱导排序（induced sorting）”思想，基于 LMS 子串递归，也是 O(n)，但常数更小、空间更省（约 3n 或更少），是当前工程上最快的线性后缀数组构造之一。两者权衡：DC3 正确性直观、适合教学与简单实现，SA-IS 常数小、内存优、适合大规模与库实现。相对 O(n log n) 的倍增法，线性算法在超大输入上更重要。

线性构造的取舍在内存与常数。SA-IS 的诱导排序把常数压到很低，DC3 空间大但易实现大常数；工程上大文本优先 SA-IS，小规模可用倍增。

• SAM 的线性状态数（≤2n−1）
• endpos 等价类划分
• 用 link 树统计出现次数

Suffix Automaton 是接受原串所有子串的最小 DFA，状态数 ≤2n−1、转移 ≤3n−4，线性。每个状态代表一个 endpos 等价类（拥有相同“出现结束位置集合”的子串），状态内所有子串互为后缀且长度连续。出现次数统计：对每个状态维护其 endpos 集合大小，初始只有终态（原位）为 1，最后沿 link 树（fail 树上）自底向上累加，得到每个状态代表子串的出现次数。精确过程：每个位置的子串属于其所在状态，出现次数 = 该状态在 link 树上的子树 endpos 累积和。最小表示指它是接受所有子串的最小自动机。

SAM 的线性性由 endpos 等价类划分保证：每个等价类收敛成一个状态，link 树体现“最长后缀”关系。出现次数统计利用 link 树后序遍历累加是 O(n) 的关键。

• SAM 的 link 边与转移边
• 广义 SAM（多串插入）
• 多串子串计数的查询

SAM 有转移边（cnext，表示状态接受字符后到达的状态）和 link 边（后缀链接，指向最长真后缀所在状态）。link 树把状态组织成树，支持 endpos 统计、子串出现次数、最长公共子串等。广义 SAM 把多个串依次插入到同一个 SAM 上（每个串插入时重置到 root，保留已有状态），从而支持多串的公共子串、任一串的出现次数等查询；每个状态可记录“出现在哪些串中”的位信息。多串查询（如最长公共子串）可在广义 SAM 上 DP 或按 link 树统计。

link 树提供“后缀包含”层次，cnext 提供“读入字符转移”；广义 SAM 通过共享状态把多串合并，使多串子串统计在 O(总长度) 内完成。

• 朴素 Z-array 计算
• Z-box（匹配区间）维护
• 与 prefix function 的转换

Z-function 的 Z[i] 表示 s 与 s[i:] 的 LCP。朴素实现在每个位置从 0 开始比较，最坏 O(n²)。Z-box 维护当前最右匹配区间 [l,r]（即某个位置起与整串匹配的区间），处理 i 时若 i≤r 则用 Z[i−l] 初始化（受 r−i+1 限制），否则从 0 开始，扩展时更新 l,r 保证总扩展 O(n)。与 prefix function 的转换：由 Z 到 π，对每个 i>0 若 Z[i]>0 则 π[i+Z[i]−1]=max(π[i+Z[i]−1],Z[i])，再倒序做 π[i]=max(π[i],π[i+1])；反向也可由 π 通过 border 链计算 Z。两者都是 O(n)。

Z-box 是“复用已匹配区间”的分治优化，使总扩展次数线性。与 π 的转换体现了“前缀公共后缀”与“后缀公共前缀”的双重等价，边界下标差 1 需注意。

• 极端偏斜分布的 Huffman 树失衡
• 码长可能接近 n
• 长度受限修正

当符号频率极度偏斜（如一个符号占 99.9%，其余各占极少量）时，Huffman 树的合并会形成一条很长的链，个别低频符号的码长可接近符号总数 n（如频率呈斐波那契分布时，最长码长可达 n−1）。超长码字导致位宽大、解码慢、内存占用大，甚至在硬件限长（如 32 位）下不可用。长度受限 Huffman（限制最大码长 L，用 package-merge 等）在约束码长下近似最优，防止编码长度爆炸，同时控制表格与解码表大小。

极端偏斜使 Huffman 变成“长链树”，码长退化到 O(n)。length-limited 修正用次优但可控的码长换取结构与实现安全，是工程上的必要约束。

• Steiner Tree 的近似比下界
• 与 APX-hard 的关系
• 近似比下界来源

Steiner Tree 是 APX-hard 的（属于常数近似但无 PTAS 除非 P=NP），但它并非“强不可近似”（即近似比不是无穷大，而是某个常数下界）。已知除非 P=NP，Steiner Tree 不存在近似比低于 96/95（约 1.0105）的多项式算法，这是通过归约自 3SAT 或 Max-3SAT 的条件性下界；同时它存在 2-近似（MST）与 11/7≈1.55 近似，因此近似比下界是常数而非不可逼近。Karp 列表中的问题并非都有强不可近似性，Steiner Tree 因有常数近似而属于“可近似但非 PTAS”一类。

“强不可近似”指近似比无界（误差放大到任意大），而 Steiner Tree 有常数近似（2、1.55），故只是 APX-hard（常数下界），不是强不可近似。下界 96/95 来自条件性归约。

• NP 完全性是最坏情况的理论下界
• 实际实例常有结构/参数利于求解
• 近似、启发式、参数化算法

NP 完全性意味着“最坏情况下无多项式算法（除非 P=NP）”，但实践中大量实例可解：反例一，实际输入规模小（如几十个变量的 SAT、几十个城市的 TSP），蛮力/分支受限即可；反例二，很多实例有结构（平面图、稀疏、有界树宽），可用参数化算法（FPT）或平面图算法；反例三，实际实例可用近似/启发式（2-approx TSP、贪心、模拟退火、局部搜索）得到工程上可接受的高质量解。因此理论 NP 完全性不阻碍工程化，工程上靠规模、结构、近似与启发式绕开最坏情况。

理论下界针对“最坏实例”，工程用“平均实例的结构、小规模、近似与启发式”应对。这是 P vs NP 理论在实践中的正确理解：NP 完全 ≠ 不可用。

• SAP 与 Dinic 的关系
• 常数因子与 GAP 启发式
• 调试性与模板性

SAP（Shortest Augmenting Path）是 Dinic 的“无显式分层”的实现变体：用 BFS 逐步找最短增广路，配合 GAP 启发式（层标号断档即终止）与当前弧优化，实测常数小、在很多图（尤其单位容量、稀疏图）上比显式分层 Dinic 更快。SAP 模板代码简洁、无需单独建分层数组，调试与移植容易；GAP 在层断档时提前收敛，避免大量无效增广。竞赛与工程中常用 SAP/GAP 模板因为它常数优、写起来短、正确性易验证，是 Dinic 的实用等价形态。

Dinic 的显式分层与 SAP 的隐式标号在理论上等价，但 SAP+GAP 简化实现、改善常数，并保留 Dinic 的复杂度上界。这正是“理论算法到工程/竞赛落地”的经典优化。

• backward search 的 O(|P|) 迭代
• 每步 rank 的常数开销
• 块大小对空间/时间权衡

FM-Index 的 backward search 对模式每个字符做一次 LF 映射，因此 O(|P|) 次迭代，理论线性。但每次 LF 需要 rank 操作（在 L 列统计某字符出现次数），而 rank 的实现依赖 checkpoint（稀疏的 occurrence 数组）与 bitvector 的 rank/select 数据结构，常数很大。块大小（checkpoint 间隔）决定折中：块越小（间隔越近）rank 越快但占用更多空间（发生次数数组更密）；块越大越省空间但每次 rank 需扫描更长块，常数更大。因此总查询常数 = O(|P| × rank 常数)，块大小在空间与时间间权衡。

理论线性只给了迭代次数，实际常数由 rank 的块内扫描决定。设计中位块大小使空间与查询时间平衡，是 FM-Index 工程的精髓。

• 归约的语义保真（sat ⇔ 有解）
• 变量/子句组件的局部分解
• 可逆映射与构造

归约 3SAT→HAMILTON-CYCLE 用“变量组”与“子句组”构造，每个变量用一组节点，子句用“陷阱”节点，通过选择路径方向编码变量真假，保证 3SAT 可满足当且仅当图存在哈密顿圈。HAMILTON-CYCLE→TSP 把“是否存在圈”化为“边权 0/1 的 TSP 是否存在 ≤ 0 的环”。3SAT→SUBSET-SUM 用数字编码把每个子句与变量表示成十进制/二进制各位，使“和等于目标”恰好对应满足赋值。避免泄漏的核心是双向蕴含（实例可满足 ⇒ 构造有解，构造有解 ⇒ 找到原解）且构造多项式、可逆（从构造的解反推原变量赋值），各组件互不干扰（变量、子句、目标位独立）。

归约若“泄漏”意味着正反向不成立（构造有解但原问题无解或有解但构造失真）。通过独立组件+双向蕴含+可逆反推，保证归约语义保真，这是 NP 完全性证明的正否。

• 每子句建三角形（3 节点），变量对建立冲突边
• 独立集 ↔ 满足赋值
• 已知归约的组合（3SAT→IS→VC→CLIQUE→HAMPATH）

3SAT→INDEPENDENT-SET：每个子句建一个三角形（3 个节点，各代表一个字面量），给每个变量 x 与其否定 ¬x 之间加冲突边；则图存在大小为子句数的独立集当且仅当 3SAT 可满足（独立集每三角形取 1 个未被冲突的字面量）。反过来独立集也能恢复赋值（选中的字面量设为真）。VERTEX-COVER 与 CLIQUE 与独立集互补（补图、n−k 关系），可互相转化。HAMPATH 由 3SAT 经“变量组/子句组”的路径编码构造。可逆性通过“每个构造组件的选择唯一对应原变量/子句决策”实现，双向蕴含保证。

三角形+冲突边是“每个子句选一个真字面量且不冲突”的图编码，可逆性来自组件选择与赋值的一一对应。归约链（3SAT→IS→VC→CLIQUE→HAMPATH）组合公开已知归约，保持多项式可逆。

• PARTITION 是 SUBSET-SUM 的特例
• KNAPSACK 看作若干物品的价值/重量
• 可逆性与多项式保持

SUBSET-SUM 是“从集合中选子集使和等于目标 T”。PARTITION 是目标 T=总和/2 的特例，可把 SUBSET-SUM 归约到 PARTITION（加两个“差补”元素使总和变为偶数并对应目标）。KNAPSACK 把 SUBSET-SUM 的每个数看作物品（重量=价值=该数），目标即背包容量，则 SUBSET-SUM 有解当且仅当存在物品组合价值恰好等于容量。BIN-PACKING 把 SUBSET-SUM 归约成“两个箱子容量为目标”的装箱。这些归约保持多项式（构造 O(n) 新增元素）且可逆（从 PARTITION/KNAPSACK/BIN-PACKING 的解读回 SUBSET-SUM 的子集），因为目标与容量一一对应、元素集合保持不变。

PARTITION/KNAPSACK/BIN-PACKING 都是 SUBSET-SUM 的结构扩展，通过把“目标”编码成“容量/目标”并保持元素集合，保证归约双向成立且多项式可逆。

• FM-Index 的支持子串搜索
• hybrid SA-Tree 的混合结构
• 适用负载

FM-Index 基于 BWT 的 backward search，支持任意子串（含前缀/后缀/中缀）的出现次数与定位，空间紧凑（可压缩），适合大规模文本、内存受限、需要频繁子串计数的负载（如基因组、压缩检索）。hybrid Suffix Array-Tree 结合后缀数组与后缀树/字典树，用前缀树快速过滤前缀匹配、后缀数组处理后缀/中缀，平衡点查与范围查询，适合需要同时支持前缀搜索与后缀搜索且查询模式多样的负载。选择：FM-Index 适合压缩+子串计数，hybrid SA-Tree 适合混合查询模式、查询更灵活。

两种都是“紧凑索引支持子串检索”。FM-Index 空间占优、适合子串计数；hybrid 结构时间灵活、适合混合前缀/后缀查询。负载取决于查询模式与内存预算。

• 二部图最大匹配 = 单位容量网络最大流
• Konig 定理：最大匹配 = 最小点覆盖
• 任务分配的工程建模

二部图最大匹配可建模为单位容量网络：源→左部、左部→右部、右部→汇，所有边容量 1，最大流即最大匹配。Konig 定理：二部图中最大匹配大小 = 最小点覆盖大小（等价于最大独立集 = n − 最大匹配）。工程上，任务分配（如岗位-人员、课程-教室、工人-任务）建模为二部图，最大匹配找最多可完成的任务；最小点覆盖/最大独立集用于找最关键的资源或最大可闲置集合。Dinic/HK 在单位容量图上 O(E√V) 求解。

单位容量网络把最大流简化为匹配，Konig 定理给出匹配与点覆盖的对偶，使任务分配的多角度优化（最多任务、最少关键资源）统一到同一图模型上。

• cache-oblivious B 树的分块递归
• LSM 的顺序写+压缩
• buffered repository tree 的批量缓冲

cache-oblivious B 树（如 van Emde Boas 布局的 B 树）用递归分块使内存层级未知也达到最优 I/O，点查 O(log_B n) 次 I/O，插入 O(log_B n)；LSM（log-structured merge tree）把插入缓冲到内存、flush 成有序运行、后台压缩合并，写 I/O 低但读路径需查多层；buffered repository tree 用内存缓冲批量排空到外存节点，支持批量插入与批量查询，做批量操作时 I/O 优。差异：COB 树面向单点操作、缓存未知；LSM 面向写密集、顺序写；buffered repository tree 面向批量操作（batch insert/query）。

三者都是外存数据结构，但优化目标不同：COB 树用内存布局优化单点访问，LSM 用顺序写换写吞吐，buffered repository tree 用批量缓冲分摊 I/O。选型取决于负载的读写模式与批量性。

• 构造嵌套量词模式
• 测量匹配时间随输入增长
• 经典灾难性回溯模式

测试正则引擎最坏情况：构造带嵌套量词/嵌套重复的模式（如 (a+)+$、(a|a)b、(a)b、(a|a?)+$ 等），用大量 'a' 加结尾不匹配字符的输入测量时间，观察时间是否随输入长度指数增长（而非线性）。真实反例：模式 ^(a+)+$ 对输入 "aaaa...aaaab"（大量 a 后跟 b）会指数级回溯——每个 a+ 分块方式都尝试拆解，最终路径数 2^n。其他：^(a|a?)+$、^(a)*b$ 同理。这些是 ReDoS 攻击与正则拒绝服务的典型。

灾难性回溯源于“等价重言通配”的多个嵌套量词产生指数级尝试路径。步数测试（输入长度翻倍、耗时暴涨）能识别指数退化，防御用 NFA 模拟引擎或增加回溯上限。

• Euler 公式 V−E+F=2
• 4 色定理与面着色
• 平面图子图同构的多项式算法

Euler 公式 V−E+F=2 给平面图强约束（E ≤ 3V−6），用于推导平面图平均度、边数上界。4 色定理说平面图可 4 着色，面着色可转化为对偶图的点着色。平面图子图同构（如平面 H 是否包含在平面 G 中）可利用平面性：G 是平面图时，用平面图分离器（Lipton-Tarjan）做分治，或利用有界树宽与平面嵌入，得到多项式算法（一般图子图同构是 NP 完全，但平面图版本可多项式）。这是平面分离器与平面结构在子图同构中的应用。

Euler 公式给出组合约束，4 色/面着色是不变量，分离器把平面子图同构分治成小规模。平面性带来的结构（分离器、直线嵌入）使子图同构可多项式。

• 用布尔变量编码目标/组件选择
• 约束编码成 3 子句
• 双向蕴含验证归约正确性

把目标识别/配置问题归约到 3SAT：为每个目标元素/组件分配布尔变量（如“选择组件 i”），把约束（互斥、必选、组合条件）编码成 CNF 子句，再把每个子句化简为 3-子句（引入辅助变量，如 Tseitin 变换）。验证语义保真：证明“原实例有解 ⇔ 3SAT 实例可满足”，即任意满足赋值可反推出原解（正向），且原解可构造满足赋值（反向）；同时验证约束编码无不一致（不引入额外自由度/歧义）。用小规模穷举交叉验证（枚举原解与 SAT 求解器结果一致）可工程化验证。

归约核心是“变量编码决策 + 子句编码约束 + 双向蕴含”。Tseitin 变换保证子句宽度 3 且可满足性等价，穷举小实例验证是工程上验证语义保真的可靠手段。

• 分裂边界（满节点、最后一个）
• 合并/借键边界
• 最小度与孤儿节点

覆盖 B 树分裂：插入使根分裂（根满）、插入使非根节点分裂（左/右兄弟）、插入节点恰好满（分裂触发）、连续插入触发多层分裂。覆盖合并/借键：删除使节点过空（少于 t−1）并从左/右兄弟借键、兄弟也过空时合并、合并导致根下移/树高减少、删除根唯一键。左右边界：分裂发生在最左/最右子节点、合并是左/右兄弟、键数恰好 t−1/t/2t−1 的临界。测试断言：分裂后平衡、键序正确、父节点键更新、树高与节点数符合预期。

B 树正确性在于平衡不变量（每节点 t−1≤键≤2t−1，根例外）。边界测试聚焦“触发分裂/合并的临界键数”与“左右兄弟方向”，确保不变量与键序、指针一致。

• 最大流 = 最小割
• Menger：边/点连通度 = 最大不相交路径数
• 工程应用（网络可靠性、容错）

最大流最小割定理：最大流值 = 最小割容量，是网络分析的核心。Menger 定理：两点间最大顶点/边不相交路径数 = 最小点/边割集大小，即连通度。边连通度（去掉最少边使图不连通）、点连通度（去掉最少点）分别对应单位容量的边/点割。有向图用有向割与有向流，无向图可把每条边变两条有向边。工程应用：网络可靠性分析（最少故障点/链路使断网）、容错路由、集群的最少故障边界、任务分配的最大吞吐。用最大流计算连通度（O(n) 次最大流或 Gomory-Hu）。

最大流与割的等价把“无向/有向连通性”变成“流值计算”，Menger 把容错能力（连通度）与最大不相交路径对应，工程上据此评估网络可靠性与关键割。

• 最小费用流模型
• successive shortest path 与 cycle canceling 算法
• cost scaling 大规模算法

最小费用流在带单位成本的网络上求满足流量需求的最小成本流，建模物流运输、排产调度（每单位货物流成本=成本）。successive shortest path 每次用最短路（Dijkstra+势能）增广，复杂度 O(F·E log V)（F 为流量），适合小流量/单位容量；cycle canceling 先求可行流再消去负费用环，适合有负环需修正；cost scaling 用成本缩放迭代，复杂度 O(E·V·log(最大成本))，适合大规模、成本差异大的网络。选型：小规模/单位成本用 successive shortest path，有负环或需通用用 cycle canceling，大规模物流/排产用 cost scaling 或带势能的最短路。

三条算法在“增广方式与复杂度”上取舍：successive 每一步最短路、cycle canceling 消环、cost scaling 按成本缩放批量增广。选型取决于流量规模、成本结构与负环存在性。

• BM 的从右向左+跳跃
• 多模式的后缀树/trie 结合
• 最坏情况与 AC 的对比

Commentz-Walter 把 Boyer-Moore 的“从右向左匹配 + 坏字符/好后缀跳跃”思想扩展到多模式：把模式集合建 trie（或后缀树），从文本扫描位置从右往左匹配，命中时用跳跃表跳过大段不匹配区域。它利用“坏字符在任一模式中是否出现”决定跳跃，平均优秀。但它没有主导 AC 的原因：最坏情况是 O(n·m)（m 为最长模式），不如 AC 的 O(n+命中) 最坏线性；构造复杂（需后缀树+跳跃表）、常数大、内存多；对文本随机、模式短时跳跃优势不明显。因此工程上 AC 靠最坏线性与简单实现占据主导，Commentz-Walter 主要在特定平均场景有优势。

AC 的“线性最坏 + 简单 trie+failure”更稳健，Commentz-Walter 的跳跃只在平均上有优势但最坏退化和复杂度高。稳健性胜过平均优势，故 AC 主导。

• 字符块（block）大小 B
• shift 表与 hash 表
• 稀疏跳跃减少误命中

Wu-Manber 是 BM 的多模式扩展：把模式末尾 B 个字符作为一个块（block），用 hash 映射到 shift 表（记录该块模式可向右跳多远）与 hash 表（该块对应的模式候选）。匹配时从文本末尾取 B 字符块，查 shift 表决定跳跃距离；若 shift 指示可能命中，则查 hash 表拿候选模式做精确匹配。B 大小（常 2~4）影响跳跃粒度与误命中率：B 大则 shift 值大、跳跃多但哈希表可能冲突；用稀疏的 hash 表（只存出现过的块）减少内存与误命中。大字典上靠大 shift（长尾字符块罕见）与 hash 表过滤把误命中压到很低。

Wu-Manber 用“块哈希 + 跳跃表”实现多模式的平均跳跃，B 与 hash 表设计控制误命中与内存。稀疏表只存实际块，避免大字典内存爆炸。

• 弦图（完美消除序）与完美图
• 间隔图（区间表示）
• 树宽与最小填充

弦图（chordal graph）是每个长度 >3 的圈都有弦（弦连接圈上非相邻点）的图，可用完美消除序（PEO）判定与构造（贪心 MCS 算法）。完美图是每个导出子图都满足诱导子图色数=团数的图，包含弦图、间隔图、二分图补图等。间隔图是弦图特例（顶点为区间，边表相交），可用区间排序判定。树宽刻画图的“树状松弛”，树宽小的图可用动态规划；最小填充（fill-in）是加最少边使图变弦图，与树宽相关（k 树宽对应弦图别）。平面图是另一类（可平面嵌入），与弦图不同。判定：MCS 找 PEO 判弦图、区间图判相交、树宽用消去/分支定界估算。

这些图类通过“序/表示/树状结构”刻画：弦图=PEO、间隔图=区间表示、完美图=coloring 性质、树宽=树分解。最小填充与弦图、树宽直接相关，是 NP 难的但小树宽可算。

• 模式集规模与预处理
• 文本库规模与查询方式
• 各算法的内存/时间取舍

5GB 文本库、模式集固定（如敏感词/病毒库）用 AC 自动机：预处理 O(总模式长度) 建 trie+failure，在线扫描 O(n+命中)，内存 O(总模式长度×字符集)，最坏线性、稳健，适合一次性扫描整个库。若模式集很大且文本长、需平均跳跃，Wu-Manber 平均更快但最坏退化、需哈希表。Suffix Automaton 构建 O(总长度) 但需先建文本的 SAM（5GB 文本 → 内存巨大），不适合整库；若改成对模式建 SAM 或对文本块建 SAM 则可做子串查询。综合：固定大量模式、全库扫描选 AC；模式多且文本随机的平均场景可 Wu-Manber；需要子串定位/出现次数（而非整词匹配）且内存允许才考虑 SAM/FM-Index。

5GB 文本决定索引内存与构建时间优先。AC 占内存<模式长度×字符集、构建快、全库扫描线性，是最稳选择；Wu-Manber 表面快但内存/最坏代价大；SAM 整库内存不可行。选型看模式性质与查询类型。

• NFA 模拟的线性时间
• 回溯引擎的实现特性
• 功能与性能取舍

NFA 模拟（Thompson/Pike，如 RE2）把正则编译成 NFA，逐字符维护“当前活跃状态集合”，每字符 O(活跃状态数)，最坏线性但可能较大；它支持捕获组（Pike VM）但牺牲回溯引用等高级特性。回溯式引擎（PCRE、Java、ICU）用递归回溯按模式顺序尝试，支持反向引用、回溯引用、lookaround 等丰富特性，但最坏指数（灾难性回溯）。性能差异：NFA 模拟对任意输入线性、抗 ReDoS，回溯引擎对常见输入快（常数小、可优化）但病态输入指数爆炸。工程上，安全敏感/不可信输入用 NFA 模拟，需高级特性时用回溯并限制输入或回溯上限。

NFA 模拟把“路径搜索”压缩为“状态集合并行推进”，时间线性之代价是特性受限；回溯引擎语法丰富但代价是潜在指数。选型是功能与安全性/性能的权衡。

• 循环同构串的最小表示
• Lyndon 分解与最小表示的关系
• 线性时间实现

循环同构串的最小表示（最小旋转）是串的所有循环移位中字典序最小的一个。Duval 算法基于 Lyndon 分解：把串分解成若干 Lyndon 词（每个词严格小于其所有真后缀）。可在线性时间内（双指针比较）求得最小旋转：构造 s+s，用 Lyndon 分解的 Duval 比较找到最小旋转的起始位置。Lyndon 分解本身 O(n)，它与最小表示、KMP 等关系密切。实现：用 i,j,k 三个指针比较，遇到相等延长、遇到更小/更大更新起点，总 O(n)。

Lyndon 词的性质（最小后缀即自身）使最小旋转可在分解中找到：最小旋转的起点是 Lyndon 分解中某个词的起点。Duval 的线性比较是工程标准。