Myers 差分算法（图搜索视角） ​

参考：The Myers diff algorithm: Part 2（James Coglan）

在做什么 ​

给定序列 A（长度 N）和 B（长度 M），diff 要找一条最短的「编辑脚本」（Shortest Edit Script, SES）：用最少步的「删除 A 中字符 / 插入 B 中字符」把 A 变成 B。
等价地，可以看成在编辑图上从 (0,0) 走到 (N,M) 的最短路径问题；路径上的斜边越多，说明**匹配（保留）**越多，总步数越少。

（与「最长公共子序列」LCS 对偶：SES 最短 ⟺ 保留的匹配最多。）

编辑图怎么建 ​

顶点为坐标 (x, y)，其中 x ∈ [0,N] 表示已处理 A 的前 x 个字符，y ∈ [0,M] 表示已处理 B 的前 y 个。

• 横移 (x, y) → (x+1, y)：只在 A 上前进 → 表示从 A 删除当前这一格对应的字符（未在 B 的已对齐部分消耗）。
• 纵移 (x, y) → (x, y+1)：只在 B 上前进 → 表示向结果中插入 B 的当前字符。
• 斜移 (x, y) → (x+1, y+1)：当 A[x] === B[y]（按 0-based 下标理解「下一对待齐字符」）时允许 → 匹配 / 保留，不计为插入或删除。

从 (0,0) 到 (N,M) 的任意一条路径，都对应一种合法变换；斜边条数最大的路径对应最长公共子序列，其非斜边步数最少的路径就是 Myers 要找的 SES。

例：经典演示里 A = "ABCABBA"、B = "CBABAC"。在图上走斜线表示两个串当前位置字符相同，可以「一起吃掉」。

为何叫「Myers」：按「编辑距离 d」扩圈，而不是存整张图 ​

朴素图搜索要维护大量分支。Myers 的关键是：不必显式展开所有路径，而是用按层（编辑步数 d）的思想，在每条「对角线」k = x - y 上只记录当前 d 下能到达的最远 x（或等价地最远 (x,y)）。

• 同一层 d 上，所有可达点满足「非斜步数 = d」；先横/纵再尽量蛇形吃斜线（能匹配就连续斜走），可以在 O(1) 摊销意义下更新最远点。
• 时间：最坏约 O((N+M) × D)，其中 D 为 SES 长度（编辑距离）；差异很小时很快。
• 空间（只要长度 / 终点）：只需长度与 O(N+M) 量级相关的数组（随实现细节为 O(N+M) 或 O(D) 量级的一维表），不必存全图。

若还要输出完整编辑序列，回溯时往往需要保存每一层 d 的整表快照；最坏情况下层数与路径信息可导致空间上升到约 O((N+M)²)（与「存下整张动态规划表」同量级）。这也是后续线性空间版本要解决的问题。

小结 ​

下一篇：线性空间的 Myers（分治 + 中间蛇）。