最长公共子序列长度c++

最长公共子序列（Longest Common Subsequence, LCS）是指两个或多个序列中最长的共同部分，但这些元素不需要连续。在C++中计算两个字符串的LCS通常会采用动态规划的方法。KMP算法、Boyer-Moore算法等也可以用于特定场景。

下面是一个简单的C++函数，使用了二维数组来存储中间结果，寻找两个字符串之间的最长公共子序列：

#include <string>
#include <vector>

std::size_t lcsLength(const std::string& str1, const std::string& str2) {
    int m = str1.length();
    int n = str2.length();

    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 (str1[i - 1] == str2[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]);
            }
        }
    }

    return dp[m][n];
}

这个函数返回`str1`和`str2`的最长公共子序列的长度。如果你想找到具体的子序列，可以在动态规划过程中记录每个位置的选择，但这将增加复杂度。