求最长公共子序列c语言实现，要求输出长度和符合条件的全部序列

求最长公共子序列 (Longest Common Subsequence, LCS) 是一个经典的计算机科学问题，通常通过动态规划算法解决。在 C 语言中，可以编写递归或迭代的方式来找到两个字符串之间的最长公共子序列。以下是简单的迭代版本的实现：

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

// 定义函数，返回字符串s1和s2的LCS的长度
int lcsLength(char* s1, char* s2) {
    int m = strlen(s1);
    int n = strlen(s2);

    // 初始化一个二维数组dp，其中dp[i][j]表示s1前i个字符和s2前j个字符的LCS长度
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];  // 返回LCS的长度
}

// 辅助函数，打印所有可能的LCS，这里仅返回长度
void printLCS(char* s1, char* s2, int m, int n, int i, int j, int len) {
    if (len == 0 || i == m || j == n) {
        return;
    }

    if (s1[i - 1] == s2[j - 1]) {
        printf("%c", s1[i - 1]);  // 打印当前字符
        printLCS(s1, s2, i - 1, j - 1, i, j, len + 1);  // 递归继续寻找子序列
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
        printLCS(s1, s2, i - 1, j, i, j, len);  // 如果左上角更长，跳过当前字符
    } else {
        printLCS(s1, s2, i, j - 1, i, j, len);  // 否则从右上角开始
    }
}

int main() {
    char s1[] = "ABCDGH";
    char s2[] = "AEDFHR";

    int lcsLengthResult = lcsLength(s1, s2);
    printf("The length of the longest common subsequence is %d\n", lcsLengthResult);

    if (lcsLengthResult > 0) {
        printf("Possible LCS sequences: ");
        printLCS(s1, s2, strlen(s1), strlen(s2), strlen(s1), strlen(s2), lcsLengthResult);
        printf("\n");
    }

    return 0;
}

上述代码首先计算了两个字符串的最长公共子序列的长度，然后根据这个长度递归地打印出所有符合条件的子序列。注意，由于存在多个可能的LCS，这里的实现只输出一个，通常是最后一个找到的。