给定 2个序列X={x1,x2,…,xm}和 Y={y1,y2,….,yn},找出X和Y的最长公共子序列.写出基本思想和源程序，用c语言

给定两个序列 X 和 Y 的最长公共子序列（Longest Common Subsequence, LCS）问题是寻找这两个序列中最长的、同时存在于两个序列中的连续子序列。基本思想通常采用动态规划（Dynamic Programming）的方法求解。

基本思想：
1. 定义一个二维数组 `dp[i][j]`，其中 `dp[i][j]` 表示序列 X 的前 i 个元素和序列 Y 的前 j 个元素的最长公共子序列长度。
2. 遍历矩阵 `dp`，对于每个位置 `(i, j)`：
- 如果 `xi = yj`，那么当前字符属于公共子序列，所以 `dp[i][j] = dp[i-1][j-1] + 1`。
- 否则，如果 `xi` 和 `yj` 不相等，则选择继续在各自序列中延伸，即 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`。
3. 最终的 LSCS 长度就是 `dp[m][n]`，而实际的子序列可以通过回溯找到。

以下是简单的 C 语言实现：

#include <stdio.h>

// 功能：计算两个字符串的最长公共子序列长度
int lcs(char *X, char *Y, int m, int n) {
    int dp[m+1][n+1];
    
    // 初始化矩阵
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }

    return dp[m][n];
}

// 主函数演示如何获取并打印LCS
void find_lcs(char *X, char *Y, int m, int n) {
    int lcs_len = lcs(X, Y, m, n);
    char lcs_str[lcs_len + 1]; // 存储子序列的空间
    lcs_str[lcs_len] = '\0'; // 结束标志

    // 回溯构建LCS
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            lcs_str[lcs_len-1] = X[i-1];
            i--;
            j--;
            lcs_len--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    printf("Longest common subsequence: %s\n", lcs_str);
}

int main() {
    char X[] = "ABCDGH";
    char Y[] = "AEDFHR";
    int m = strlen(X), n = strlen(Y);
    find_lcs(X, Y, m, n);
    return 0;
}

在这个例子中，输入序列 X 和 Y 分别是 "ABCDGH" 和 "AEDFHR"，程序将返回它们的最长公共子序列 "ADH"。