最长公共子序列长度是什么 c++

最长公共子序列（Longest Common Subsequence, LCS）是指两个序列中最长的那个相同元素组成的序列，但这些元素不一定连续出现。在C++中，计算两个字符串的LCS通常会使用动态规划算法。经典的KMP算法、Hirschberg分割或者直接使用二维数组（如二维字符数组或者自定义数据结构）通过填充表格的方式来求解。

`std::string` 类型可以直接用于动态规划计算，创建一个二维数组 `dp[i][j]` 表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列长度。算法的基本思路是从左上角开始遍历，如果当前字符匹配则 dp[i][j] = dp[i-1][j-1]+1，如果不匹配，则取较大者 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

以下是简单的C++代码片段：

#include <string>
int lcs(std::string str1, std::string str2) {
    int m = str1.size();
    int n = str2.size();
    int dp[m + 1][n + 1];
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else 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];
}