最长公共子序列c++

以下是C++代码实现最长公共子序列（LCS）：

#include<bits/stdc++.h> 
using namespace std; 

int lcs( char *X, char *Y, int m, int n ) 
{ 
    int L[m+1][n+1]; // 创建一个二维数组来存储LCS的长度

    // 构建L[m+1][n+1]的表格，用于存储LCS的长度
    for (int i=0; i<=m; i++) 
    { 
        for (int j=0; j<=n; j++) 
        { 
            if (i == 0 || j == 0) // 初始化首行和首列
                L[i][j] = 0; 

            else if (X[i-1] == Y[j-1]) // 如果当前字符相等，则LCS长度加1
                L[i][j] = L[i-1][j-1] + 1; 

            else // 如果当前字符不相等，则LCS长度等于前一行或前一列的最大值
                L[i][j] = max(L[i-1][j], L[i][j-1]); 
        } 
    } 

    return L[m][n]; // 返回LCS的长度
} 

int main() 
{ 
    char X[] = "AGGTAB"; 
    char Y[] = "GXTXAYB"; 

    int m = strlen(X); 
    int n = strlen(Y); 

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

    return 0; 
} 

上述代码输出结果为:

Length of LCS is 4

其中，`X`和`Y`分别是需要比较的两个字符串，`m`和`n`分别是它们的长度。`L[m+1][n+1]`是一个二维数组，用于存储LCS的长度。在函数`lcs()`中，我们首先初始化`L[0][j]`和`L[i][0]`。接着，我们在循环中比较当前字符是否相等，如果相等，则LCS的长度加1，否则LCS的长度等于前一行或前一列的最大值。最后，我们返回`L[m][n]`，即LCS的长度。