实验2.2 最长公共子序列 问题描述： 给定两个序列X={x1,x2,...,xm}和Y={y1,y2,...,yn},找出X和Y的最长公共子序列。 输入： 第1行：两个子序列的长度，m n 第2行：第1个子序列的各个元素（序列下标从1开始） 第3行：第2个子序列的各个元素（序列下标从1开始） 输出： 最长公共子序列 实例： 输入： 第1行： 4 5 //m和n的值 第2行 abad //输入4个字符，下标从1开始 第3行 baade //输入5个字符，下标从1开始 输出： aad c 语言实现

以下是 C 语言实现最长公共子序列的代码：

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

#define MAX_LENGTH 100

int lcs(int m, int n, char X[], char Y[], int c[][MAX_LENGTH], int b[][MAX_LENGTH]) {
    int i, j;
    for (i = 0; i <= m; i++)
        c[i][0] = 0;
    for (i = 0; i <= n; i++)
        c[0][i] = 0;
    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;
                b[i][j] = 0;
            }
            else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 1;
            }
            else {
                c[i][j] = c[i][j - 1];
                b[i][j] = -1;
            }
        }
    }
    return c[m][n];
}

void print_lcs(int i, int j, char X[], int b[][MAX_LENGTH]) {
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == 0) {
        print_lcs(i - 1, j - 1, X, b);
        printf("%c", X[i - 1]);
    }
    else if (b[i][j] == 1)
        print_lcs(i - 1, j, X, b);
    else
        print_lcs(i, j - 1, X, b);
}

int main() {
    char X[MAX_LENGTH], Y[MAX_LENGTH];
    int c[MAX_LENGTH][MAX_LENGTH], b[MAX_LENGTH][MAX_LENGTH];
    int m, n, i, j, len_lcs;

    scanf("%d%d", &m, &n);
    for (i = 0; i < m; i++)
        scanf(" %c", &X[i]);
    for (i = 0; i < n; i++)
        scanf(" %c", &Y[i]);

    len_lcs = lcs(m, n, X, Y, c, b);
    print_lcs(m, n, X, b);

    return 0;
}

代码中使用了动态规划算法，利用一个二维数组 c 存储最长公共子序列的长度，利用另一个二维数组 b 存储状态转移的信息，用于回溯输出最长公共子序列。

首先，将 c 和 b 数组的第一行和第一列初始化为 0。然后，从第二行和第二列开始依次计算每个位置的值，如果当前位置的字符相同，则最长公共子序列的长度加 1，同时在 b 数组中标记状态为 0，表示从左上角转移过来。如果当前位置的字符不同，则最长公共子序列的长度不变，需要从 c 数组中选择较大的值进行转移，同时在 b 数组中标记状态为 1 或 -1，表示从上方或左方转移过来。最后，利用 b 数组回溯输出最长公共子序列即可。

注意，由于输入中可能包含空格字符，所以需要在 scanf 函数中加上空格字符来忽略空格。另外，由于数组下标从 0 开始，所以需要在计算 c 和 b 数组时需要使用 X[i-1] 和 Y[j-1] 来表示当前位置的字符。