最大公共子序列问题C++代码加注释

// 这段C++代码解决的是最大公共子序列(Matching Subsequence, 缩写MS)问题，它不是最长公共子序列(Longest Common Subsequence, 缩写LCS)，后者是指两个序列中最长的公共部分，而MS只要求存在公共子序列即可。

#include <iostream> // 包含输入输出流
#include <vector> // 包含向量容器，方便处理子序列
using namespace std;

// 动态规划函数，计算给定字符串x和y的最大公共子序列
vector<int> getMaxCommonSubsequence(string x, string y) {
    int m = x.size(), n = y.size(); // 计算字符串长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 初始化动态规划矩阵

    // 遍历矩阵，填充dp值
    for (int i = 1; i <= m; i++) { // x的索引
        for (int j = 1; j <= n; j++) { // y的索引
            // 如果当前字符相等，则最大公共子序列增加1，并取前一对的位置的DP值
            if (x[i - 1] == y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            // 否则，取前一对的较大值作为当前的MS长度
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 通过dp矩阵构建最大公共子序列，回溯过程
    vector<int> res; // 存储结果
    int i = m, j = n;
    while (i > 0 && j > 0) {
        // 当前字符相等，将其添加到结果序列
        if (x[i - 1] == y[j - 1])
            res.push_back(x[i - 1]), i--, j--;
        // 不相等，向左上方移动
        else if (dp[i - 1][j] > dp[i][j - 1])
            i--;
        else
            j--;
    }

    reverse(res.begin(), res.end()); // 因为回溯是从右下角开始，所以结果需要反转
    return res;
}

int main() {
    string str_x = "ABCBDAB", str_y = "BDCAB"; // 示例字符串
    vector<int> result = getMaxCommonSubsequence(str_x, str_y); // 调用函数获取结果

    cout << "最大公共子序列: ";
    for (const auto& ch : result)
        cout << ch << "; ";
    cout << endl;

    return 0;
}