矩阵动态规划-最长公共子序列(LCS)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/**************************************************************** 
 * Description: LCS  最大公共子序列
 * Author: Alex Li
 * Date: 2024-04-06 10:20:00
 * LastEditTime: 2024-04-06 12:06:43
****************************************************************/
#include <iostream>
using namespace std;

vector<vector<int> > dp; // 声明一个二维动态规划数组dp，用于存储LCS的长度信息。

// LCS函数计算并返回两个字符串X和Y的最长公共子序列的长度。
int LCS(string X, string Y, int m, int n){
     // 使用动态规划填充dp数组。
     for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(X[i-1]==Y[j-1]){
                // 如果当前字符匹配，则当前LCS长度是左上角值加一。
                dp[i][j]=dp[i-1][j-1]+1;               
            }
            else {
                // 如果当前字符不匹配，取左边和上边的最大值。
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
     }
     // 返回dp表的最后一个值，即为X和Y的最长公共子序列长度。
     return dp[m][n];
}

// printLCS函数使用dp表从后向前追踪并打印出最长公共子序列。
void printLCS(string X, string Y, int m, int n) {
    int index = dp[m][n]; // 获取LCS的长度。
    string lcs(index, '#'); // 初始化一个长度等于LCS长度的字符串，暂时以'#'填充。

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            // 如果字符匹配，则是LCS的一部分，添加到lcs字符串中。
            lcs[index - 1] = X[i - 1];
            i--; j--; index--; // 同时向左上角移动。
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--; // 向上移动。
        } else {
            j--; // 向左移动。
        }
    }
    cout << lcs; // 打印LCS字符串。
}

int main(){
    string x, y; // 输入的两个字符串。
    cin >> x >> y; // 从标准输入读取两个字符串。
    int m, n;
    m = x.size(); // 获取字符串x的长度。
    n = y.size(); // 获取字符串y的长度。
    dp.resize(m+1, vector<int>(n+1, 0)); // 初始化dp数组大小，所有值初值为0。
    cout << LCS(x, y, m, n) << '\n'; // 计算并打印LCS的长度。
    printLCS(x, y, m, n); // 根据dp数组打印出LCS。
}