数据布局之字符串的最长公共子序列题目详解与示例（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 语言实现

1. #include <stdio.h>
2. #include <string.h>
4. void printLCS(char X[], char Y[], int dp[][100]) {
5.     int m = strlen(X);
6.     int n = strlen(Y);
7.     int i, j;
8.     for (i = m, j = n; i > 0 && j > 0; i--, j--) {
9.         if (X[i - 1] == Y[j - 1]) {
10.             printf("%c", X[i - 1]);
11.             X++;
12.             Y++;
13.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
14.             i--;
15.         } else {
16.             j--;
17.         }
18.     }
19. }
21. int LCSLength(char X[], char Y[], int m, int n) {
22.     int dp[100][100];
23.     int i, j;
25.     // 初始化动态规划表
26.     for (i = 0; i <= m; i++) {
27.         dp[i][0] = 0;
28.     }
29.     for (j = 0; j <= n; j++) {
30.         dp[0][j] = 0;
31.     }
33.     // 动态规划填表
34.     for (i = 1; i <= m; i++) {
35.         for (j = 1; j <= n; j++) {
36.             if (X[i - 1] == Y[j - 1]) {
37.                 dp[i][j] = dp[i - 1][j - 1] + 1;
38.             } else {
39.                 dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
40.             }
41.         }
42.     }
44.     // 打印最长公共子序列
45.     printLCS(X, Y, dp);
47.     return dp[m][n];
48. }
50. int main() {
51.     char X[] = "AGGTAB";
52.     char Y[] = "GXTXAYB";
53.     int m = strlen(X);
54.     int n = strlen(Y);
55.     printf("最长公共子序列的长度为 %d\n", LCSLength(X, Y, m, n));
56.     return 0;
57. }

复制代码

C++ 语言实现

1. #include <iostream>
2. #include <vector>
3. #include <string>
5. std::string LCS(const std::string& X, const std::string& Y) {
6.     int m = X.length();
7.     int n = Y.length();
8.     std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
9.     std::string lcs;
11.     // 动态规划填表
12.     for (int i = 1; i <= m; i++) {
13.         for (int j = 1; j <= n; j++) {
14.             if (X[i - 1] == Y[j - 1]) {
15.                 dp[i][j] = dp[i - 1][j - 1] + 1;
16.             } else {
17.                 dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
18.             }
19.         }
20.     }
22.     // 构建最长公共子序列
23.     int i = m, j = n;
24.     while (i > 0 && j > 0) {
25.         if (X[i - 1] == Y[j - 1]) {
26.             lcs += X[i - 1];
27.             i--;
28.             j--;
29.         } else if (dp[i - 1][j] > dp[i][j - 1]) {
30.             i--;
31.         } else {
32.             j--;
33.         }
34.     }
36.     // 输出结果
37.     std::reverse(lcs.begin(), lcs.end());
38.     std::cout << "最长公共子序列是： " << lcs << std::endl;
39.     return lcs;
40. }
42. int main() {
43.     std::string X = "AGGTAB";
44.     std::string Y = "GXTXAYB";
45.     std::string lcs = LCS(X, Y);
46.     return 0;
47. }

复制代码

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

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

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