C++实现最长公共子序列

最长公共子序列（LCS）问题是在两个序列中找到一个最长的子序列，使得这个子序列在两个序列中都出现。下面是C++实现LCS的代码：

#include <iostream>
#include <cstring>
using namespace std;

int lcs(string X, string Y, int m, int n) {
    int L[m + 1][n + 1];
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    return L[m][n];
}

int main() {
    string X = "AGGTAB";
    string Y = "GXTXAYB";
    int m = X.length();
    int n = Y.length();

    cout << "Length of LCS is " << lcs(X, Y, m, n) << endl;
    return 0;
}

这个代码使用了动态规划的思想，通过计算L[i][j]来找到最长公共子序列的长度。其中，L[i][j]表示X[0...i-1]和Y[0...j-1]的LCS的长度。

首先，我们初始化L[0][j]和L[i][0]为0，因为空串和任何字符串的LCS长度都为0。

然后，我们从1到m和1到n遍历整个字符串，如果X[i-1]与Y[j-1]相等，那么L[i][j]等于L[i-1][j-1]加1，否则L[i][j]等于L[i-1][j]和L[i][j-1]中的较大值。

最终，L[m][n]就是最长公共子序列的长度。