C语言最长公共子序列代码改进意见

为了改进C语言最长公共子序列代码，可以考虑以下几点：

1.使用动态规划算法，将时间复杂度从指数级别降低到多项式级别。

2.使用一维数组代替二维数组，减少空间复杂度。

3.在动态规划过程中，只需要记录当前行和上一行的信息，因此可以使用滚动数组的方式进一步减少空间复杂度。

4.在回溯过程中，可以使用栈来存储最长公共子序列，避免递归调用带来的额外开销。

下面是一个改进后的C语言最长公共子序列代码的示例：

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

#define MAX_LEN 100

int lcs_length(char *X, char *Y, int m, int n, int *c) {
    int i, j, k;
    int *p1, *p2, *tmp;
    p1 = (int *)malloc((n + 1) * sizeof(int));
    p2 = (int *)malloc((n + 1) * sizeof(int));
    for (i = 0; i <= n; i++) {
        p1[i] = 0;
        p2[i] = 0;
    }
    for (i = 1; i <= m; i++) {
        tmp = p1;
        p1 = p2;
        p2 = tmp;
        p2[0] = 0;
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                p2[j] = p1[j - 1] + 1;
            } else if (p1[j] >= p2[j - 1]) {
                p2[j] = p1[j];
            } else {
                p2[j] = p2[j - 1];
            }
        }
    }
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            c[i * (n + 1) + j] = p2[j];
        }
    }
    k = p2[n];
    free(p1);
    free(p2);
    return k;
}

void lcs(char *X, char *Y, int m, int n, int *c, char *result) {
    int i, j, k;
    int *stack = (int *)malloc(k * sizeof(int));
    k = c[m * (n + 1) + n];
    i = m;
    j = n;
    while (k > 0) {
        if (X[i - 1] == Y[j - 1]) {
            stack[k - 1] = i - 1;
            i--;
            j--;
            k--;
        } else if (c[(i - 1) * (n + 1) + j] >= c[i * (n + 1) + j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    for (i = 0; i < k; i++) {
        result[i] = X[stack[i]];
    }
    result[k] = '\0';
    free(stack);
}

int main() {
    char X[MAX_LEN], Y[MAX_LEN], result[MAX_LEN];
    int m, n, k;
    int c[(MAX_LEN + 1) * (MAX_LEN + 1)];
    printf("请输入序列X：");
    scanf("%s", X);
    printf("请输入序列Y：");
    scanf("%s", Y);
    m = strlen(X);
    n = strlen(Y);
    k = lcs_length(X, Y, m, n, c);
    printf("最长公共子序列长度为：%d\n", k);
    lcs(X, Y, m, n, c, result);
    printf("最长公共子序列为：%s\n", result);
    return 0;
}