Electrolux_blogMyers 差分的线性空间版本（Linear Space）
参考：Myers diff in linear space: theory（James Coglan）
文内「liner」常写作 linear，指空间与
N+M成线性关系，而不是平方。
要解决什么
标准 Myers 在需要完整编辑路径时，若对每一层 d 都保存整张向量以便回溯，最坏可能占用约 O((N+M)²) 空间。
线性空间算法在仍基于 Myers 的「对角线 + 编辑距离」框架下，把构造整条 SES 的空间压到 O(N+M)（通常还需 O(N+M) 的辅助缓冲；常数依实现而定）。
核心想法：分治（Divide & Conquer）
不再把问题看成「一次性求出一条全局最长匹配链并从头回溯」，而是：
求一条「中间蛇」（middle snake）
在编辑图上，找到穿过「中点」某条对角线的一条最优路径片段（论文/博文里对「中点」有精确定义：与(N/2, M/2)相关的分层中点）。
这一步仍可用 Myers 的双向搜索（从起点正向、从终点反向各算一组最远点），但只保留当前层向量，不把历史层全部存盘。用这条蛇把矩形区域切成两块
蛇的左端对应子问题「A左段 ↔B左段」，右端对应「A右段 ↔B右段」。
原问题的一条最优 SES，可以由左子问题的 SES + 中间蛇上的匹配 + 右子问题的 SES 拼成。递归直到平凡
子问题规模下降，最终落到空串或可直接求解的小块，再自底向上拼回完整 diff。
因此：一个全局 LCS/SES 问题被拆成多个更小实例上的同一类问题；每一层递归只做线性量的工作并常数个「中间蛇」查找，从而控制总空间。
与 01-myer.md 的对比
| 维度 | 基本 Myers（带完整回溯表） | 线性空间 Myers |
|---|---|---|
| 思路 | 按 d 扩圈，必要时存每层状态回溯 | 找中间蛇 + 递归子矩形 |
| 时间 | 典型 O((N+M)D)，最坏情形与实现相关 | 同量级常数通常更大（递归与双向搜索） |
| 空间 | 路径回溯最坏可到约 O((N+M)²) | 输出整条 diff 时仍保持 O(N+M) 量级 |
小结
线性空间版本没有换一种 diff 语义，仍是 Myers 那套图模型；变的是如何在不保存全部历史层的前提下，用分治 + 中间蛇把结果拼出来。
若只关心编辑距离或长度，基本 Myers 的一维表就够；若要在大文件上生成完整 unified diff 又卡内存，才更值得上这一套。
相关：基本 Myers 图模型。