最长公共子序列问题：算法与代码实现

最长公共子序列问题：算法与代码实现

题目描述

给定两个序列 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 最长公共子序列: acbdb

算法思路

1、建立两个二维数组 L 和 S，L 数组记录公共子序列的长度，S 数组记录 L 数组的状态。 2、状态转移方程： 1)、当 x[i] == y[j] 时，L[i][j] = L[i-1][j-1] + 1，S[i][j] = 1。 2)、当 x[i] != y[j] 时，L[i][j] = max(L[i-1][j], L[i][j-1])，S[i][j] = 2 或 3。 3、从 S 数组中反推出公共子序列。

C++ 代码

#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, L[m + 1][n + 1];
    printf("请输入 X 序列长度:");
    scanf("%d", &m);
    char x[m + 1];
    printf("X 序列:");
    scanf("%s", x);
    printf("请输入 Y 序列长度:");
    scanf("%d", &n);
    char y[n + 1];
    printf("Y 序列:");
    scanf("%s", y);
    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("\n");
    }
    printf("最长公共子序列长度：%d\n", len);
    printf("最长公共子序列:");
    for (int i = 0; i < len; i++)
        printf("%c ", z[i]);
    return 0;
}

总结

本文介绍了最长公共子序列问题的定义、算法思路和 C++ 代码实现。通过动态规划方法，使用两个二维数组记录子序列长度和状态，并最终反推出最长公共子序列。该算法简单易懂，代码实现较为简洁，适用于解决不同序列的最长公共子序列问题。