ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据布局之字符串的最长公共子序列题目详解与示例（C,C++） [打印本页]

作者: 惊雷无声 时间: 2024-7-24 08:52
标题: 数据布局之字符串的最长公共子序列题目详解与示例（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 = Y[j] 时，dp[j] = dp[i-1][j-1] + 1；
当 X != Y[j] 时，dp[j] = max(dp[i-1][j], dp[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[j-1] 表现 X[1…i-1] 和 Y[1…j] 的公共子序列长度。
初始化

初始化 dp[0][j] = 0 （对于所有 0 <= j < m）和 dp[0] = 0 （对于所有 0 <= i < n），因为任何序列与一个空序列都有一个公共子序列长度为0。
构建最长公共子序列

根据动态规划表，我们可以从 dp[n][m] 开始，逆向追踪得到最长公共子序列 Z[1…n+m]。当我们得到 dp[j] 时，有两种环境：
如果 X = Y[j]，则 Z[k] = X 而且 k++，然后我们递归地求 dp[i-1][j-1]；
如果 X != Y[j]，则我们分别递归地求 dp[i-1][j] 和 dp[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题目可以扩展到多个字符串的环境，也可以结合其他算法优化求解过程，如后缀数组、后缀树等。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4