稀疏 LCS · O(K²)

稀疏性：只在 match point 上递推

省空间：滚动数组与 Hirschberg 分治在同一张编辑距离表上做减法，减的是内存，时间仍要 $O(mn)$ 。本页减时间。切入点是 Erickson 在附录 D.2 开头的观察：许多 DP 实例里，绝大多数子问题都以完全相同的方式被解决，值得计算的格子只占少数，这样的实例称为稀疏（sparse）。LCS 的表是标准样本——整张表可以只由 $A[i] = B[j]$ 的位置重建，位置足够少时，逐格填满就是浪费。

1 · 不许替换的编辑距离

编辑距离有插入、删除、替换三种操作。把替换禁掉，或者等价地把一次替换记成「删一步加插一步」，最优编辑脚本的目标就变成最大化免费的对位：两串中保持相对顺序一致、无需任何操作的字符。这组字符构成两串的公共子序列，最长者即 LCS（longest common subsequence，最长公共子序列）；记其长度为 $L$ ，禁替换的编辑距离等于 $m + n - 2L$ 。求 $L$ 的递推与编辑距离同一个骨架，同属序列对齐 DP：一张表跑出四种算法那张三来源网格：

\mathit{LCS}(i,j) = \begin{cases} 0 & i = 0 \text{ 或 } j = 0 \\ \mathit{LCS}(i-1,\,j-1) + 1 & A[i] = B[j] \\ \max\{\mathit{LCS}(i-1,\,j),\ \mathit{LCS}(i,\,j-1)\} & \text{其余} \end{cases}

逐格填表的时间是 $O(mn)$ 。本页贯穿使用一对样本串 ALGORITHMS 与 ALTRUISTIC（ $m = n = 10$ ）：经典填表恰好计算 100 格，得 $L = 5$ ，回溯出的一条公共子序列是 ALRIT。

2 · match point 与整表重建

$A[i] = B[j]$ 的下标对 $(i, j)$ 称为 match point（匹配点），它们是递推里唯一能让值增长的格子；其余格子只是把左、上两个方向的既有值搬运过来，不携带新信息。整张表于是可以只由匹配点重建：

\mathit{LCS}(i,j) = \begin{cases} 0 & i = j = 0 \\ \max\{\mathit{LCS}(i',j') \mid A[i'] = B[j'],\ i' < i,\ j' < j\} + 1 & A[i] = B[j] \\ \max\{\mathit{LCS}(i',j') \mid A[i'] = B[j'],\ i' \le i,\ j' \le j\} & \text{其余} \end{cases}

第二行的不等号是严格的，第三行的不是：一个匹配点要引用别的匹配点必须严格错开一行一列，而普通格子允许把同行同列的匹配点原值搬来。为了让两个 $\max$ 永不落空，书中在两串首尾各接一个不与任何真实字符相同的哨兵（sentinel）——记作「«」与「»」。首哨兵在 $(0, 0)$ 处配出全表的公共起点，尾哨兵在 $(m+1, n+1)$ 处配出公共终点，此后只需在匹配点上求值，答案是 $\mathit{LCS}(m+1, n+1) - 1$ 。

哨兵这一层在引用书中数字时要自己剥掉。附录的图 D.1 给 ALGORITHMS 与 ALTRUISTIC 画出整张 memoization 表，右下角标红的值是 6；本页锁定测试的初版照抄这个 6 当 LCS 长度，与经典填表对照的断言当场失败。那个 6 是含哨兵的 $\mathit{LCS}(m+1, n+1)$ ，剥掉哨兵才是真实长度 5。这条教训以注释留在 engines.test.ts 的 sparse 组里。

3 · 匹配点的排序归并求法

匹配点的个数记作 $K$ 。直接暴力枚举全部下标对要 $O(mn)$ 次比较，与填表同阶，稀疏的便宜还没占到就先还了回去。FindMatches 用排序绕开：两串各自按字符排序、随身携带原始下标，然后像归并排序的合并阶段一样推进双游标，字符不等时较小的一侧前进，相等时两侧的同字符块做笛卡尔积、整块吐出匹配点。排序花 $O(m \log m + n \log n)$ ，归并线性，吐点与点数成正比，合计 $O(m \log m + n \log n + K)$ 。

样本串之间 $K = 8$ ：字符「A」「L」「R」「S」各在两串出现一次，各配出一个点；「I」与「T」在 ALTRUISTIC 里各出现两次，各配出一个 ${1 \times 2}$ 的块。归并吐出的点按字符序排列，下一步递推却要按行主序扫描，core/sparse.ts 在收尾用一行 sort 统一重排。

图 3-1 · FindMatches 的排序归并。上下两条是按字符排序后的

A

与

B

（小字为原始下标），字符不等时较小一侧的游标前进，相等时两个同字符块整体配对、把匹配点吐进右侧

m \times n

网格。可切换预设观察不同字符构成下匹配点的疏密。

4 · 稀疏递推的账本

把匹配点按 lex 序（行主序）逐个求值：轮到某点时，行列都更小的匹配点全部算完，取「严格左上」前驱的最大值加一；收尾对全体值取一次 $\max$ ，等价于在尾哨兵处求值。sparseLCS 对每个点扫描全部前驱，账本恰好是 $\binom{K}{2}$ 次两两配对加 $K$ 次收尾比较：样本串 $K = 8$ ，合计 ${28 + 8 = 36}$ 次，对照经典填表的 100 格。36 与 100 都锁进了 engines.test.ts 的快照，改引擎或预设必须同步改本页正文。

排序项之外的主导代价是 $O(K^2)$ ，只有 $K = o(\sqrt{mn})$ 时稀疏递推才真正胜过填表，条件比直觉的「 $K$ 小于 $mn$ 就行」苛刻得多。字符集一小、重复一多， $K$ 就会失控：极端的 AAAA 对 AAA，每个下标对都是匹配点， $K = 4 \times 3 = 12$ 与 $mn$ 相等， $\binom{12}{2} = 66$ 次扫描是 12 格全表的五倍以上。失败也不必等到 $K = mn$ ：MISSISSIPPI 对 SASSAFRAS 只在字母「S」上配点，两串各含 4 个「S」， $K = 16$ 远小于 $mn = 99$ ，但 $\binom{16}{2} = 120$ 次扫描仍超过 99 格。胜负线不是画在 $K < mn$ ，而是画在 $\sqrt{mn}$ 附近。

书中习题还留了一档：配合阈值数组上的二分查找，递推项可以再从 $K^2$ 压到 $K \log K$ ；这条线的经典文献是 Hunt–Szymanski 算法，总时间 $O((K + n)\log n)$ [2]。本页不展开。

图 4-1 · SparseLCS 在匹配点上的递推。网格里只有 match point 参与计算，经典表淡化为灰色底；红框为当前点，虚线蓝框为本步扫过的候选，实心蓝框为选中的严格左上前驱，末帧把回溯链连成一条公共子序列并拼出字符串。可改写两串或选预设，AAAA 对 AAA 演示

K

膨胀到

mn

时扫描次数反超填表。

5 · 参考文献

Erickson, J. (2019). Advanced dynamic programming. In Algorithms, Appendix D. 全书公开于 algorithms.wtf，附录 D 的本地副本随本系列存放（D-faster-dynprog.pdf）。
Hunt, J. W., & Szymanski, T. G. (1977). A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5), 350–353.