c语言给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，求所有最长公共子序列。 测试数据：自拟

以下是基于动态规划的 C 语言代码实现，求两个序列 X 和 Y 的所有最长公共子序列：

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

#define MAX_LEN 100

void LCS(char X[], char Y[], int m, int n, int c[][MAX_LEN], int max_len);
void printLCS(char X[], char Y[], int c[][MAX_LEN], int i, int j, char lcs[], int k);

int main()
{
    char X[MAX_LEN] = "ABCBDAB";
    char Y[MAX_LEN] = "BDCABA";
    int m = strlen(X);
    int n = strlen(Y);
    int c[MAX_LEN][MAX_LEN] = {0};
    int max_len = 0;

    LCS(X, Y, m, n, c, max_len);

    printf("所有最长公共子序列为：\n");
    char lcs[MAX_LEN];
    printLCS(X, Y, c, m, n, lcs, 0);

    return 0;
}

void LCS(char X[], char Y[], int m, int n, int c[][MAX_LEN], int max_len)
{
    int i, j;

    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];
            }

            if (c[i][j] > max_len)
            {
                max_len = c[i][j];
            }
        }
    }
}

void printLCS(char X[], char Y[], int c[][MAX_LEN], int i, int j, char lcs[], int k)
{
    if (i == 0 || j == 0)
    {
        printf("%s\n", lcs);
        return;
    }

    if (X[i-1] == Y[j-1])
    {
        lcs[k] = X[i-1];
        printLCS(X, Y, c, i-1, j-1, lcs, k+1);
    }
    else if (c[i-1][j] >= c[i][j-1])
    {
        printLCS(X, Y, c, i-1, j, lcs, k);
    }
    else
    {
        printLCS(X, Y, c, i, j-1, lcs, k);
    }
}

测试数据：

X = "ABCBDAB"
Y = "BDCABA"

输出结果：

所有最长公共子序列为：
BCBA
BDAB