Hirschberg 线性空间序列比对

任意从左上角到右下角的合法路径都要经过中间行。设最优路径在该行经过 $(p,b_0+j)$。到这个点之前的费用至少是 $F[j]$，之后至少是 $R[j]$；另一方面，两条分别最优的子路径又确实能在该点连接。因此

这个等式就是切分证书。即使一条路径沿中间行走过多个格点，取其中任何一个都仍是合法切口；不要求每条路径只穿线一次。

普通分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。往往先按输入大小切开，再处理两边。本方法必须先做两次分数计算，才能知道目标串应该在哪里切开。左右两块不是任意拼接：中线最小和保证至少存在一条全局最优路径经过共同角点。

两行数值怎样恢复删除位置 ​

令 $A=\mathtt{\text{CABACDA}}$、$B=\mathtt{\text{ABCDA}}$。源串切在第三个字符后，左半为 CAB，右半为 ACDA。对应目标串切点 $j=0,1,2,3,4,5$ 的费用为

最小和为 $2$，切点 $j^{\ast }=2$。于是递归问题是 CAB 对 AB，以及 ACDA 对 CDA。前一块再把 CAB 切成 C 与 AB，最优目标切点为零，直接删除第一个 C。后一块删除开头的 A，剩余 CDA 全部配对。连接后是

长度差已经给出至少两次删除的下界，因此结果与最小费用一致。更重要的是，每个具体删除位置都是由中线费用和递归基例恢复的，并未保留全部格点的父指针。

平局与费用方向 ​

有多个最小和时，最左切点只是确定性约定，不保证与完整表“先对角”的回溯得到相同脚本。验收应比较生成的目标串和总费用。若费用不对称，交换源串与目标串以缩短行宽时，必须同时交换插入、删除的含义及费用；带方向的替换费用也要转置。单位对称费用下，转换回原方向时仍须把插入与删除互换，并交换每条操作记录中的源字符与目标字符；替换 $a\to b$ 因而变成 $b\to a$。匹配保持同一字符，操作流的左右次序不变。

反向计算同样是在原编辑图上求从中线到终点的费用。若费用依赖字符位置，简单反转字符串以后重新按新位置收费可能算错；应反向访问原图边，并保持原代价。具有仿射空隙费用的比对还要把“当前是否处于空隙”等状态带到切口，不能只用一个标量 $F[j]+R[j]$。

时间为什么没有多乘一个对数 ​

一层中线计算做 $O(mn)$ 个格子。随后源串近乎平分，目标串分成长度 $j^{\ast }$ 与 $n-j^{\ast }$；两个子矩形的面积和约为 $mn/2$。逐层相加是几何级数，而不是每层重复处理整块面积。计入奇数长度、基例扫描和输出，时间为 $O((m+1)(n+1))$。

空间要把数组、栈和输出分开 ​

开始时让较短串作为滚动行宽度。每个递归结点只保存整数范围，不复制子串；选定切点后先释放前向、反向及求和数组，再进入两个孩子。于是工作数组为 $O(min(m,n)+1)$。本页下载实现用常数条长度为 $n+1$ 的数组，示例最大工作数组上界为 $18$ 个数；用于展示的可选追踪记录不计入节省空间的运行模式。

递归只平分源串，调用栈深度为 $O(1+\log (max(m,n)+1))$。因此这份直接递归实现的辅助空间严格写成

另外还有最多 $m+n$ 条输出操作。若把输入与输出一起算，总空间为线性；“只留两行”不意味着连递归帧和输出都不存在。把每层数组留在父栈帧中，或为图示永久保存全部中线数组，都会改变实际存储界。

这种用数值重算换取路径存储的思路适合长序列比对，也适合其他能沿分隔面组合前向与后向最优值的网格问题。关键不是矩形外观，而是切口状态足以连接两边，且连接后的费用确实可加。