最长公共子上升序列c++

最长公共子序列（Longest Common Subsequence, LCS）是指两个或多个序列中最长的公共部分，它们并不一定连续，只是顺序相同。在C++中，计算LCS通常采用动态规划算法来解决，特别是使用二维数组来存储中间结果。

KMP（Knuth-Morris-Pratt）算法是一种改进的版本，用于快速查找字符串之间的LCS，它避免了不必要的回溯。以下是简单的C++代码示例：

#include <iostream>
#include <vector>

std::string lcs(std::string X, std::string Y) {
    int m = X.size();
    int n = Y.size();
    std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 从右下角开始构建LCS序列
    std::string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            result += X[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result; // 返回反转后的LCS序列
}

int main() {
    std::string str1 = "ABCDGH";
    std::string str2 = "AEDFHR";
    std::cout << "LCS of " << str1 << " and " << str2 << " is: " << lcs(str1, str2) << std::endl;
    return 0;
}