最长公共子序列 (LCS) 算法详解及 C 代码实现

问题描述: 给定两个序列 X = (x1, x2, ..., xm) 和 Y = (y1, y2, ..., yn)，当另一个序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。根据已知两个序列，求二者公共最长子序列。

输入格式: 序列 X 和序列 Y

输出格式: 公共最长子序列及长度、求解问题过程中填写的表中数据

输入示例: 请输入 X 序列长度: 6 X 序列: 'abcbdb' 请输入 Y 序列长度: 9 Y 序列: 'acbbabdbb'

输出示例: 表中数据如下: 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 2 2 2 2 2 2 2 0 1 2 2 2 2 2 2 2 2 0 1 2 3 3 3 3 3 3 3 0 1 2 3 3 3 3 4 4 4 0 1 2 3 4 4 4 4 5 5 最长公共子序列长度：5 最长公共子序列: 'a c b d b'

代码实现:

#include<stdio.h>

int CommonOrder(char x[],int m,char y[],int n,char z[])
{
    int i,j,k,L[m+1][n+1],S[m+1][n+1];
    for(j=0;j<=n;j++)
        L[0][j]=0;
    for(i=0;i<=m;i++)
        L[i][0]=0;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(x[i]==y[j])
            { L[i][j]=L[i-1][j-1]+1;S[i][j]=1; }
            else if(L[i][j-1]>=L[i-1][j])
            { L[i][j]=L[i][j-1];S[i][j]=2;    }
            else{ L[i][j]=L[i-1][j];S[i][j]=3; }
    i=m;j=n;k=L[m][n];
    while(i>0&&j>0)
    {
        if(S[i][j]==1){ z[--k]=x[i];--i;--j;}
        else if(S[i][j]==2) --j;
        else --i;
    }
    return L[m][n];
}

int main()
{
    int m,n;
    printf("请输入 X 序列长度:");
    scanf("%d",&m);
    char x[m+1];
    printf("X 序列:");
    scanf("%s",x+1);
    printf("请输入 Y 序列长度:");
    scanf("%d",&n);
    char y[n+1];
    printf("Y 序列:");
    scanf("%s",y+1);
    char z[m+n+1];
    int len=CommonOrder(x,m,y,n,z);
    printf("表中数据如下:
");
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
            printf("%d  ",L[i][j]);
        printf("
");
    }
    printf("最长公共子序列长度：%d
",len);
    printf("最长公共子序列:");
    for(int i=1;i<=len;i++)
        printf("%c ",z[i]);
    printf("
");
    return 0;
}

代码说明:

CommonOrder 函数实现 LCS 算法，使用动态规划方法计算最长公共子序列长度和序列。
L 数组存储所有子问题的结果，S 数组记录当前子问题最优解是由哪种情况得到。
main 函数负责输入输出。

总结: 本文详细讲解了 LCS 算法的原理和实现，并提供了 C 代码示例。通过学习该算法，读者可以更好地理解动态规划的应用以及最长公共子序列问题的解决方法。