经典算法——最长公共子序列

大家好，欢迎来到IT知识分享网。

最长公共子序列（Longest Common Subsequence, LCS）

一、概念与定义

最长公共子序列（LCS）是两个或多个字符串的最长子序列，其中字符之间的相对顺序保持不变，但不一定连续。例如，在字符串 “ABCBDAB” 和 “BDCAB” 中，LCS 是 “BCAB”。

二、解决方法与动态规划

使用动态规划求解最长公共子序列问题，其基本步骤如下：

1. 初始化状态转移表：

创建一个二维数组 dp，其中 dp[i][j] 表示字符串 str1 的前 i 个字符和字符串 str2 的前 j 个字符的最长公共子序列的长度。

2. 定义状态转移方程：

如果 str1[i-1] 等于 str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符可加入到LCS中。

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示不考虑当前字符时，取之前计算的最大LCS长度。

3. 边界条件：

• 当 i == 0 或 j == 0 时，即其中一个字符串为空，此时最长公共子序列长度为0。

4. 构建LCS：

根据状态转移表逆向追溯得到实际的LCS字符串。

C++ 示例代码片段

#include <iostream> #include <vector> using namespace std; // 计算两个字符串的最长公共子序列长度并返回状态转移表 vector<vector<int>> lcsLength(const string& str1, const string& str2) { int m = str1.size(), n = str2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp; } // 根据状态转移表重建最长公共子序列 string buildLCS(const vector<vector<int>>& dp, const string& str1, int i, int j) { if (i == 0 || j == 0) { return ""; } else if (str1[i - 1] == str2[j - 1]) { return buildLCS(dp, str1, i - 1, j - 1) + str1[i - 1]; } else { if (dp[i - 1][j] > dp[i][j - 1]) { return buildLCS(dp, str1, i - 1, j); } else { return buildLCS(dp, str1, i, j - 1); } } } int main() { string str1 = "ABCBDAB"; string str2 = "BDCAB"; // 计算LCS长度并获取状态转移表 vector<vector<int>> dp = lcsLength(str1, str2); // 重建并打印最长公共子序列 string lcs = buildLCS(dp, str1, str1.size(), str2.size()); cout << "The Longest Common Subsequence is: " << lcs << endl; return 0; }

上述代码首先通过 lcsLength 函数计算出状态转移表，然后利用该表以及 buildLCS 函数来递归地重建最长公共子序列。在实际应用中，还可以对代码进行优化以提高效率。