这一篇是队友所看的论文，稍作整理。
空间压缩
首先纠正上一篇中的一处错误，空间可以压缩到 O(n) ，然而同时就意味着不能得到具体序列。当不在乎具体序列时可以简单使用对 i 模2的方法压缩空间。
此文提供了一种方法在不提高复杂度的前提下压缩空间并能回求序列的方案。
不回求序列的压缩法
将上一篇所提到的 f[0..n][0..m] 中的第一维用 i mod 2 替换，则只有0和1，然而不影响正确性。
算法思想
将 A 二分，用不回求序列的压缩法求 A[0..n/2] 和 B[0..m] 的公共子序列长度，将所有的 f[(n/2)%2][0..m] 的值（共 m+1 个）保存为 L1[0..m]。
同理，将 A[n/2+1..n] 和 B[0..m] 倒序后得到长度 L2[m..0]。
找到 B 数组的中间值 k ，使得 L1[k]+L2[n-k] 取得最大值。
那么我们就知道了，用 A[0..n/2] 和 B[0..k] 匹配，A[n/2+1..n] 和 B[k+1..m] 匹配便可得到最长的公共子序列。
那我们递归处理A[0..n/2] 和 B[0..k] 以及 A[n/2+1..n] 和 B[k+1..m] 的匹配就可以得到最终字符串了。
当然，递归的最后需要特判 A 序列长度为0和1的情况。
伪代码
注：ALG B指的是上文所说的 i mod 2 的压缩空间的方法。
算法分析
显然空间只有O(m)；
时间略微有些复杂。用了两次 不回求序列的压缩法 ，复杂度为 O(mn)，然而每次递归复杂度递减为上一次的一半，求和后可以知道总复杂度只有O(2mn)，常数不看，即O(mn).
论文来自
A Liner Space Algorithm for Computing Maximal Common Subsequences
—— D.S. Hirschberg (Princeton University)