最长公共子序列c语言 并输出子序列

最长公共子序列 (Longest Common Subsequence, LCS) 是指两个序列中最长的相同元素序列，但它们的相对位置可以不同。在 C 语言中，计算最长公共子序列通常通过动态规划算法实现，例如著名的「Hunt-Hibbard」或「Kruskal-Jong」算法。

以下是一个简单的 C 语言函数，使用动态规划计算两个字符串的最长公共子序列：

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

// 定义一个二维数组用于存储中间结果
int lcsTable[101][101];

void findLCS(char str1[], char str2[], int m, int n) {
    // 初始化表中的值为 0
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                lcsTable[i][j] = 0;
            else if (str1[i - 1] == str2[j - 1])
                lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1;
            else
                lcsTable[i][j] = max(lcsTable[i - 1][j], lcsTable[i][j - 1]);
        }
    }
}

// 为了输出子序列，我们可以从右下角开始回溯
void printLCS(char str1[], char str2[], int m, int n) {
    if (m == 0 || n == 0)
        return;

    if (str1[m - 1] == str2[n - 1]) {
        printf("%c", str1[m - 1]);
        printLCS(str1, str2, m - 1, n - 1);
    } else if (lcsTable[m - 1][n] > lcsTable[m][n - 1]) {
        printLCS(str1, str2, m - 1, n);
    } else {
        printLCS(str1, str2, m, n - 1);
    }
}

int main() {
    char str1[] = "ABCBDAB";
    char str2[] = "BDCAB";
    int m = strlen(str1);
    int n = strlen(str2);

    findLCS(str1, str2, m, n);
    printf("Length of LCS is %d\n", lcsTable[m][n]);

    printf("LCS is: ");
    printLCS(str1, str2, m, n);
    printf("\n");

    return 0;
}

在这个示例中，`findLCS` 函数用于计算最长公共子序列的长度，`printLCS` 函数则是用来按照原顺序打印出这个子序列。当你运行这个程序，会输出给定字符串 "ABCBDAB" 和 "BDCAB" 的最长公共子序列。