c语言最长公共子序列伪代码

以下是C语言求解最长公共子序列的伪代码：

1. 首先定义一个函数Lcs_length，该函数接受两个字符串str1和str2以及两个指向指针的指针c和b作为参数，其中c和b用于存储最长公共子序列的长度和路径信息。

2. 在Lcs_length函数中，首先获取str1和str2的长度，然后创建一个二维数组c，用于存储最长公共子序列的长度，以及一个二维数组b，用于存储路径信息。

3. 然后使用两个for循环遍历str1和str2的所有字符，如果当前字符相同，则将c[i][j]设置为c[i-1][j-1]+1，并将b[i][j]设置为左上角。

4. 如果当前字符不同，则将c[i][j]设置为max(c[i-1][j], c[i][j-1])，并将b[i][j]设置为c[i-1][j] > c[i][j-1] ? 上方 : 左方。

5. 最后返回c和b。

6. 定义一个函数Find_Lcs，该函数接受两个字符串str1和str2作为参数。

7. 在Find_Lcs函数中，首先调用Lcs_length函数获取最长公共子序列的长度和路径信息。

8. 然后根据路径信息，倒序遍历c数组，将最长公共子序列存储到一个字符数组中。

9. 最后输出最长公共子序列的长度和内容。

// 定义Lcs_length函数
int Lcs_length(char *str1, char *str2, int **c, int **b) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int i, j;
    for (i = 0; i <= len1; i++) {
        c[i][0] = 0;
    }
    for (j = 0; j <= len2; j++) {
        c[0][j] = 0;
    }
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[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[len1][len2];
}

// 定义Find_Lcs函数
void Find_Lcs(char *str1, char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int **c = (int **)malloc((len1+1) * sizeof(int *));
    int **b = (int **)malloc((len1+1) * sizeof(int *));
    int i, j;
    for (i = 0; i <= len1; i++) {
        c[i] = (int *)malloc((len2+1) * sizeof(int));
        b[i] = (int *)malloc((len2+1) * sizeof(int));
    }
    int len = Lcs_length(str1, str2, c, b);
    char *lcs = (char *)malloc((len+1) * sizeof(char));
    lcs[len] = '\0';
    i = len1;
    j = len2;
    while (i > 0 && j > 0) {
        if (b[i][j] == 0) {
            lcs[--len] = str1[i-1];
            i--;
            j--;
        } else if (b[i][j] == 1) {
            i--;
        } else {
            j--;
        }
    }
    printf("最长公共子序列长度为：%d\n", len);
    printf("最长公共子序列为：%s\n", lcs);
    free(lcs);
    for (i = 0; i <= len1; i++) {
        free(c[i]);
        free(b[i]);
    }
    free(c);
    free(b);
}