数据结构之字符串的最长公共子序列问题详解与示例（C,C++）

字符串的最长公共子序列（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问题可以扩展到多个字符串的情况，也可以结合其他算法优化求解过程，如后缀数组、后缀树等。