数据布局之字符串的最长公共子序列题目详解与示例（C,C++）
https://i-blog.csdnimg.cn/direct/e9b115d91a3c43d8ba76cdc4ce5dca87.webp#pic_center字符串的最长公共子序列（Longest Common Subsequence, LCS）是计算机科学中的一个经典题目，属于动态规划（Dynamic Programming, DP）的范畴。在本博客中，我们将详细讲解最长公共子序列的概念，并给出 C 和 C++ 语言的实现示例。
1、最长公共子序列定义
最长公共子序列题目可以如许描述：给定两个字符串序列 X 和 Y，求出它们的最长公共子序列 Z。这里的子序列指的是原序列中元素次序的连续序列，但不要求元素在原序列中连续。例如，ABCD 和 ACDF 的一个最长公共子序列是 ACD。
2、动态规划解法
动态规划是解决此类题目的一种高效方法，其根本头脑是将大题目分解为小题目，先求解小题目，然后利用这些小题目的解来构造原题目的解。对于最长公共子序列题目，我们可以用一个二维数组 dp 来存储两个字符串的前缀的公共子序列长度。
3、状态转移方程
假设我们有两个字符串 X 和 Y，动态规划表 dp[][] 的第 i 行第 j 列的元素表现 X 和 Y 的公共子序列的长度。状态转移方程如下：
[*]当 X = Y 时，dp = dp + 1；
[*]当 X != Y 时，dp = max(dp, dp)。
这里 dp 表现 X 和 Y 的公共子序列长度，dp 表现 X 和 Y 的公共子序列长度，dp 表现 X 和 Y 的公共子序列长度。
初始化
初始化 dp = 0 （对于所有 0 <= j < m）和 dp = 0 （对于所有 0 <= i < n），因为任何序列与一个空序列都有一个公共子序列长度为0。
构建最长公共子序列
根据动态规划表，我们可以从 dp 开始，逆向追踪得到最长公共子序列 Z。当我们得到 dp 时，有两种环境：
如果 X = Y，则 Z = X 而且 k++，然后我们递归地求 dp；
如果 X != Y，则我们分别递归地求 dp 和 dp，取较大的一个。
4、C 和 C++ 实现示例
下面是使用 C 和 C++ 语言实现最长公共子序列的代码示例：
C 语言实现
#include <stdio.h>
#include <string.h>
void printLCS(char X[], char Y[], int dp[]) {
int m = strlen(X);
int n = strlen(Y);
int i, j;
for (i = m, j = n; i > 0 && j > 0; i--, j--) {
if (X == Y) {
printf("%c", X);
X++;
Y++;
} else if (dp > dp) {
i--;
} else {
j--;
}
}
}
int LCSLength(char X[], char Y[], int m, int n) {
int dp;
int i, j;
// 初始化动态规划表
for (i = 0; i <= m; i++) {
dp = 0;
}
for (j = 0; j <= n; j++) {
dp = 0;
}
// 动态规划填表
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
if (X == Y) {
dp = dp + 1;
} else {
dp = (dp > dp) ? dp : dp;
}
}
}
// 打印最长公共子序列
printLCS(X, Y, dp);
return dp;
}
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 == Y) {
dp = dp + 1;
} else {
dp = (dp > dp) ? dp : dp;
}
}
}
// 构建最长公共子序列
int i = m, j = n;
while (i > 0 && j > 0) {
if (X == Y) {
lcs += X;
i--;
j--;
} else if (dp > dp) {
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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]