线性空间的 LCS 算法

Diaоsi · 2025-10-30 22:43:42 · 算法·理论

原文链接

Hirschberg 算法可以在 \mathcal{O}(nm) 的时间复杂度和 \mathcal{O}(n+m) 的空间复杂度下求出两个字符串 S 和 T 的 LCS 的一组方案。以下默认 n=|S|,m=|T| 且 n,m 同阶。

经典 LCS 动态规划算法的转移可以视作一个 DAG，以 S=\mathsf{yxxyzyzx},\,T=\mathsf{yxxyzxyzxyxzx} 为例，(i-1,j-1)\to(i,j) 的斜边表示 S[i]=T[j]，边权为 1，其平行边的边权为 0。动态规划的过程相当于是在 DAG 上求出 (0,0) 到 (n,m) 的一条最长路。下图中蓝色虚线代表了一条可行的最长路，遍历路上的斜边即能获得方案。

在经典的动态规划算法中，f(i,j) 表示 (0,0) 到 (i,j) 最长路的距离，转移方程为：

类似地，可以建反图求出 g(i,j) 表示 (n,m) 到 (i,j) 反图上最长路的距离。这样对于任意点 (i,j)，我们都可以通过 f(i,j)+g(i,j) 的方式求出经过点 (i,j) 的最长路距离。

接下来进入正题：如何用 \mathcal{O}(n+m) 的空间复杂度求出 LCS 的方案，Hirschberg 给出了一种基于分治的做法。

首先，观察到对于特定的 j，可以在 \mathcal{O}(n) 的空间下求出 f(\cdot, j)，因为 f(\cdot, j) 仅依赖于 f(\cdot,j-1)，g(\cdot,j) 同理。这启发我们固定 m/2，求出 f(\cdot,m/2) 和 g(\cdot,m/2)。下标 q\gets\arg\max_{k=1}^{n}(f(k,m/2)+g(k,m/2)) 满足 (0,0) 到 (n,m) 的最长路一定经过 (q,m/2)。

这在 \mathcal{O}(n) 的空间下求出了最长路上的一个节点 (q,m/2)，并且把原问题划分成了两个子矩形 (0,0),(q,m/2) 和 (q,m/2),(n,m)。两个子矩形是独立的，递归进行上面的算法求出最长路的方案。

接下来进行时间复杂度分析，分治后子矩形的长度和为 n，宽度均为 m/2，因此时间复杂度是：

于是我们就在 \mathcal{O}(nm) 的时间复杂度和 \mathcal{O}(n+m) 的空间复杂度下求出了 LCS 的方案。

提交记录

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int N=3010,M=30010,INF=0x3f3f3f3f;
int n,m,f[2][N],g[2][N];
string s,t;
bool cmax(int &x,int y){
    if(y>=x){x=y;return 1;}
    return 0;
}
void dp(int ux,int uy,int dx,int dy){
    if(dx==ux+1){
        for(int i=uy+1;i<=dy;i++)
            if(s[dx]==t[i]){cout<<t[i];break;}
        return;
    }
    int mid=(ux+dx)>>1;
    for(int i=uy;i<=dy;i++)
        f[0][i]=f[1][i]=g[0][i]=g[1][i]=0;
    int _i=1,_j=1;
    for(int i=ux+1;i<=mid;i++,_i^=1)
        for(int j=uy+1;j<=dy;j++){
            if(s[i]==t[j])cmax(f[_i][j],f[_i^1][j-1]+1);
            cmax(f[_i][j],max(f[_i^1][j],f[_i][j-1]));
        }
    for(int i=dx-1;i>=mid;i--,_j^=1)
        for(int j=dy-1;j>=uy;j--){
            if(s[i+1]==t[j+1])cmax(g[_j][j],g[_j^1][j+1]+1);
            cmax(g[_j][j],max(g[_j^1][j],g[_j][j+1]));
        }
    _i^=1,_j^=1;
    int pos=-1,res=0;
    for(int i=uy;i<=dy;i++)
        if(cmax(res,f[_i][i]+g[_j][i]))pos=i;
    dp(ux,uy,mid,pos);
    dp(mid,pos,dx,dy);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>s>>t;
    n=s.size(),m=t.size();
    s=" "+s,t=" "+t;
    dp(0,0,n,m);
    return 0;
}