最长公共子序列 输出所有子序列 C语言

好的，我来回答你的问题。

最长公共子序列（Longest Common Subsequence，LCS）是指在所有给定序列中同时出现的最长子序列。下面是求解最长公共子序列并输出所有子序列的 C 语言代码：

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

void printLCS(char **b, char *X, int i, int j, char *lcs, int k) {
    if (i == 0 || j == 0) {
        for (int l = k - 1; l >= 0; l--) {
            printf("%c", lcs[l]);
        }
        printf("\n");
    } else {
        if (b[i][j] == 'd') {
            lcs[k] = X[i - 1];
            printLCS(b, X, i - 1, j - 1, lcs, k + 1);
        } else if (b[i][j] == 'u') {
            printLCS(b, X, i - 1, j, lcs, k);
        } else {
            printLCS(b, X, i, j - 1, lcs, k);
        }
    }
}

void LCS(char *X, char *Y) {
    int m = strlen(X);
    int n = strlen(Y);
    int c[m + 1][n + 1];
    char **b = (char **)malloc((m + 1) * sizeof(char *));
    for (int i = 0; i <= m; i++) {
        b[i] = (char *)malloc((n + 1) * sizeof(char));
    }
    for (int i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        c[0][j] = 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 'd';
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 'u';
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = 'l';
            }
        }
    }
    char lcs[m];
    printLCS(b, X, m, n, lcs, 0);
    for (int i = 0; i <= m; i++) {
        free(b[i]);
    }
    free(b);
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCABA";
    LCS(X, Y);
    return 0;
}

这个程序使用动态规划方法求解最长公共子序列，并输出所有子序列。在 `printLCS` 函数中，`b` 数组记录了最长公共子序列的构造方式，'d' 表示从对角线方向（左上角）来的，'u' 表示从上方来的，'l' 表示从左方来的。`lcs` 数组记录当前构造的最长公共子序列，`k` 表示当前已经构造的最长公共子序列长度。当 `i` 或 `j` 等于 0 时，表示已经处理完一个序列，此时将 `lcs` 数组中的字符倒序输出即为一个最长公共子序列。