用动态规划算法求解给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，求所有最长公共子序列。给出c语言代码

以下是C语言实现最长公共子序列的动态规划算法：

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

#define MAXLEN 100

int c[MAXLEN+1][MAXLEN+1];

void LCSLength(char *x, char *y, int m, int n) {
    int i, j;
    for (i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        c[0][j] = 0;
    }
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (x[i-1] == y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else if (c[i-1][j] >= c[i][j-1]) {
                c[i][j] = c[i-1][j];
            } else {
                c[i][j] = c[i][j-1];
            }
        }
    }
}

void printLCS(char *x, int i, int j) {
    if (i == 0 || j == 0) {
        return;
    }
    if (c[i][j] == c[i-1][j]) {
        printLCS(x, i-1, j);
    } else if (c[i][j] == c[i][j-1]) {
        printLCS(x, i, j-1);
    } else {
        printLCS(x, i-1, j-1);
        printf("%c ", x[i-1]);
    }
}

int main() {
    char x[] = "ABCBDAB";
    char y[] = "BDCABA";
    int m = strlen(x);
    int n = strlen(y);
    LCSLength(x, y, m, n);
    printf("Length of LCS is %d\n", c[m][n]);
    printf("LCS is ");
    printLCS(x, m, n);
    printf("\n");
    return 0;
}

输出结果：

Length of LCS is 4
LCS is BCBA