求字符串序列“abcdbab”和“bdcaba”的最长公共子序列的C++代码实现

以下是求解最长公共子序列的C代码实现：

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
return (a > b) ? a : b;
}

int lcs(char* X, char* 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() {
char X[] = "abcdbab";
char Y[] = "bdcaba";

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

printf("Length of LCS is %d", lcs(X, Y, m, n));

return 0;
}

输出结果为：Length of LCS is 4

表示两个字符串"abcdbab"和"bdcaba"的最长公共子序列为"bcba"，长度为4。