在这里插入图片描述


字符串的最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中的一个经典问题,属于动态规划(Dynamic Programming, DP)的范畴。在本博客中,我们将详细讲解最长公共子序列的概念,并给出 C 和 C++ 语言的实现示例。

1、最长公共子序列定义

最长公共子序列问题可以这样描述:给定两个字符串序列 X 和 Y,求出它们的最长公共子序列 Z。这里的子序列指的是原序列中元素顺序的连续序列,但不要求元素在原序列中连续。例如,ABCD 和 ACDF 的一个最长公共子序列是 ACD。

2、动态规划解法

动态规划是解决此类问题的一种高效方法,其基本思想是将大问题分解为小问题,先求解小问题,然后利用这些小问题的解来构造原问题的解。对于最长公共子序列问题,我们可以用一个二维数组 dp 来存储两个字符串的前缀的公共子序列长度。

3、状态转移方程

假设我们有两个字符串 X[1…n] 和 Y[1…m],动态规划表 dp[][] 的第 i 行第 j 列的元素表示 X[1…i] 和 Y[1…j] 的公共子序列的长度。状态转移方程如下:

  • 当 X[i] = Y[j] 时,dp[i][j] = dp[i-1][j-1] + 1;
  • 当 X[i] != Y[j] 时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这里 dp[i-1][j-1] 表示 X[1…i-1] 和 Y[1…j-1] 的公共子序列长度,dp[i-1][j] 表示 X[1…i] 和 Y[1…j-1] 的公共子序列长度,dp[i][j-1] 表示 X[1…i-1] 和 Y[1…j] 的公共子序列长度。

初始化

初始化 dp[0][j] = 0 (对于所有 0 <= j < m)和 dp[i][0] = 0 (对于所有 0 <= i < n),因为任何序列与一个空序列都有一个公共子序列长度为0。

构建最长公共子序列

根据动态规划表,我们可以从 dp[n][m] 开始,逆向追踪得到最长公共子序列 Z[1…n+m]。当我们得到 dp[i][j] 时,有两种情况:

如果 X[i] = Y[j],则 Z[k] = X[i] 并且 k++,然后我们递归地求 dp[i-1][j-1];
如果 X[i] != Y[j],则我们分别递归地求 dp[i-1][j] 和 dp[i][j-1],取较大的一个。

4、C 和 C++ 实现示例

下面是使用 C 和 C++ 语言实现最长公共子序列的代码示例:

C 语言实现

#include <stdio.h>
#include <string.h>

void printLCS(char X[], char Y[], int dp[][100]) {
    int m = strlen(X);
    int n = strlen(Y);
    int i, j;
    for (i = m, j = n; i > 0 && j > 0; i--, j--) {
        if (X[i - 1] == Y[j - 1]) {
            printf("%c", X[i - 1]);
            X++;
            Y++;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
}

int LCSLength(char X[], char Y[], int m, int n) {
    int dp[100][100];
    int i, j;

    // 初始化动态规划表
    for (i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    // 动态规划填表
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    // 打印最长公共子序列
    printLCS(X, Y, dp);

    return dp[m][n];
}

int main() {
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    printf("最长公共子序列的长度为 %d\n", LCSLength(X, Y, m, n));
    return 0;
}

C++ 语言实现

#include <iostream>
#include <vector>
#include <string>

std::string LCS(const std::string& X, const std::string& Y) {
    int m = X.length();
    int n = Y.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    std::string lcs;

    // 动态规划填表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    // 构建最长公共子序列
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs += X[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    // 输出结果
    std::reverse(lcs.begin(), lcs.end());
    std::cout << "最长公共子序列是: " << lcs << std::endl;
    return lcs;
}

int main() {
    std::string X = "AGGTAB";
    std::string Y = "GXTXAYB";
    std::string lcs = LCS(X, Y);
    return 0;
}

在这两个示例中,我们首先初始化了一个动态规划表 dp,然后使用状态转移方程填充它。最后,我们通过回溯动态规划表来构建并打印最长公共子序列。在 C++ 示例中,我们使用了 std::vector 来存储动态规划表,这使得代码更加清晰和易于管理。

5、总结

本文详细介绍了最长公共子序列(LCS)问题的原理,并通过C/C++语言给出了具体的实现。LCS问题是一个经典的动态规划问题,通过构建状态转移方程,我们可以高效地求解两个字符串的最长公共子序列。在实际应用中,LCS问题可以扩展到多个字符串的情况,也可以结合其他算法优化求解过程,如后缀数组、后缀树等。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部