最长公共子序列

定义

两个或者两个以上序列的所有共同子序列最长的一个，称为最长公共子序列(Longest Common Subsequence)。

求解算法

思路

设\(a[1\ldots n]\)、\(b[1\ldots m]\)表示原序列，\(f[i][j]\)表示\(a[1\dots i]\)和\(b[1\dots j]\)的LCS。 状态转移方程： \[f[i][j]=\begin{cases} max(f[i-1][j],f[i][j-1]),\quad a[i]\neq b[j] \ f[i-1][j-1]+1,\quad a[i]=b[j] \end{cases} \] 答案为\(f[n][m]\)。 可以在更新时用链表维护一下，以便输出LCS。

实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2005;
int lena,lenb,a[MAXN],b[MAXN],ans1,ans2[MAXN];
struct node
{
    int x,nextx,nexty;
}f[MAXN][MAXN];
int main()
{
    scanf("%d",&lena);
    for(int i=1;i<=lena;++i)scanf("%d",&a[i]);
    scanf("%d",&lenb);
    for(int i=1;i<=lenb;++i)scanf("%d",&b[i]);
    for(int i=1;i<=lena;++i)
        for(int j=1;j<=lenb;++j)
        {
            if(a[i]==b[j])f[i][j]=(node){f[i-1][j-1].x+1,i-1,j-1};
            else
            {
                if(f[i-1][j].x>f[i][j-1].x)f[i][j]=(node){f[i-1][j].x,i-1,j};
                else f[i][j]=(node){f[i][j-1].x,i,j-1};
            }
        }
    printf("%d\n",f[lena][lenb].x);
    int x=lena,y=lenb;
    while(x&&y)
    {
        node temp=f[x][y];
        x=temp.nextx;y=temp.nexty;
        if(f[x][y].x==temp.x-1)ans2[++ans1]=a[x+1];
    }
    for(int i=ans1;i>=1;--i)printf("%d ",ans2[i]);
    puts("");
    return 0;
}