最长公共子序列问题 代码

### 最长公共子序列问题详解 #### 一、问题背景与定义 **最长公共子序列**(Longest Common Subsequence, LCS)问题是计算机科学中的一个重要问题，主要涉及的是两个或多个序列之间的最大相同子序列的问题。这里所说的“子序列”是指序列中的元素按原顺序排列但不要求连续的一段序列。 例如，对于两个序列`X = {A, B, C, D, G, H}`和`Y = {A, E, D, F, H, R}`，它们的一个公共子序列是`{A, D, H}`。在这个例子中，最长的公共子序列是`{A, D, H}`，长度为3。 #### 二、问题的性质 LCS问题具备以下特性： 1. **子问题的重叠性**：即通过分解后得到的子问题会出现重复的情况。 2. **最优子结构**：全局最优解可以通过局部最优解来构建。 #### 三、算法设计 ##### 1. 动态规划法 **思路概述**：本问题可通过动态规划法解决。具体来说，我们首先定义一个二维数组`C[i][j]`来记录`X`的前`i`个元素与`Y`的前`j`个元素组成的最长公共子序列的长度。接下来，我们定义如何根据`X`和`Y`的具体元素来更新这个数组。 **C[i][j]的定义**： - 如果`i = 0`或者`j = 0`，那么`C[i][j] = 0`； - 如果`X[i] = Y[j]`，那么`C[i][j] = C[i-1][j-1] + 1`； - 否则，`C[i][j] = max(C[i-1][j], C[i][j-1])`。 此外，为了追踪如何达到`C[i][j]`的值，还需要定义一个二维数组`b[i][j]`。该数组用于记录`C[i][j]`是由哪些子问题的值更新而来，从而帮助我们找到所有最长公共子序列。 **b[i][j]的定义**： - 如果`X[i] = Y[j]`，那么`b[i][j] = 1`； - 如果`C[i-1][j] < C[i][j-1]`，那么`b[i][j] = 2`； - 如果`C[i-1][j] > C[i][j-1]`，那么`b[i][j] = 3`； - 如果`C[i-1][j] = C[i][j-1]`，那么`b[i][j] = 4`。 ##### 2. 查找所有最长公共子序列 **Find_All_LCS算法**： - 基于`C`和`b`数组，我们可以采用回溯法来找出所有最长公共子序列。 - 使用辅助数组记录递归过程中得到的子序列。 - 每次递归调用时，首先检查当前子序列是否为空，如果不为空，则继续判断是否已达到最长公共子序列的长度。 - 根据`b[i][j]`的值来决定下一步的搜索方向。 - 特别注意，当`b[i][j] = 4`时，意味着需要同时沿两个方向进行搜索，以确保不会遗漏任何最长公共子序列。 #### 四、时间复杂度分析 **求解辅助数组C和b的时间复杂度**：这部分的时间复杂度为`O(mn)`，其中`m`和`n`分别是序列`X`和`Y`的长度。 **Find_All_LCS算法的时间复杂度**： - 最好情况：`m = n`且所有元素均匹配，时间复杂度为`O(n)`。 - 最坏情况：两个序列没有公共子序列，时间复杂度为`O([pic])`，其中`[pic]`代表组合数学中的路径数问题的解。 #### 五、算法实现示例 ```cpp // 文件名：FindLongestCommonSequence.cpp // 说明：求出两个序列中所有的最长公共子序列 #include <iostream> #include <vector> using namespace std; // 定义求解LCS的核心函数 void FindAllLCS(const vector<char>& X, const vector<char>& Y, int i, int j, vector<vector<int>>& C, vector<vector<int>>& b, vector<char>& currentLCS, vector<vector<char>>& allLCS) { if (i == 0 || j == 0) { allLCS.push_back(currentLCS); return; } if (b[i][j] == 1) { // 当前字符匹配 currentLCS.push_back(X[i-1]); FindAllLCS(X, Y, i-1, j-1, C, b, currentLCS, allLCS); currentLCS.pop_back(); } else if (b[i][j] == 2) { // 向左移动 FindAllLCS(X, Y, i, j-1, C, b, currentLCS, allLCS); } else if (b[i][j] == 3) { // 向上移动 FindAllLCS(X, Y, i-1, j, C, b, currentLCS, allLCS); } else if (b[i][j] == 4) { // 向左或向上 FindAllLCS(X, Y, i, j-1, C, b, currentLCS, allLCS); FindAllLCS(X, Y, i-1, j, C, b, currentLCS, allLCS); } } int main() { vector<char> X = {'A', 'B', 'C', 'D', 'G', 'H'}; vector<char> Y = {'A', 'E', 'D', 'F', 'H', 'R'}; int m = X.size(), n = Y.size(); vector<vector<int>> C(m+1, vector<int>(n+1, 0)); vector<vector<int>> b(m+1, vector<int>(n+1, 0)); // 构建C和b数组 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (X[i-1] == Y[j-1]) { C[i][j] = C[i-1][j-1] + 1; b[i][j] = 1; } else { if (C[i-1][j] >= C[i][j-1]) { C[i][j] = C[i-1][j]; b[i][j] = (C[i-1][j] == C[i][j-1]) ? 4 : 2; } else { C[i][j] = C[i][j-1]; b[i][j] = 3; } } } } vector<vector<char>> allLCS; vector<char> currentLCS; FindAllLCS(X, Y, m, n, C, b, currentLCS, allLCS); cout << "所有最长公共子序列: " << endl; for (auto& lcs : allLCS) { for (char c : lcs) { cout << c << " "; } cout << endl; } return 0; } ``` 通过上述步骤，我们可以有效地解决问题，并找出两个序列的所有最长公共子序列。