代码如下:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>int maxleng(char* a, char* b, int m, int n)//求最长公共子序列的长度
{int** dp = (int**)malloc(sizeof(int*) * (m + 1));for (int i = 0; i <= m; i++){dp[i] = (int*)malloc(sizeof(int) * (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 (a[i - 1] == b[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]);}}}int result = dp[m][n];for (int i = 0; i <= m; i++){free(dp[i]);}free(dp);return result;
}void printchar(char* a, char* b, int m, int n)//输出最长公共子序列
{int** dp = (int**)malloc(sizeof(int*) * (m + 1));for (int i = 0; i <= m; i++){dp[i] = (int*)malloc(sizeof(int) * (n + 1));}maxleng(a, b, m, n);int index = dp[m][n];char* lcs_str = (char*)malloc(sizeof(char) * (index + 1));if (lcs_str == NULL){printf("内存分配失败\n");return;}lcs_str[index] = '\0';int i = m, j = n;while (i > 0 && j > 0){if (a[i - 1] == b[j - 1]){lcs_str[--index] = a[i - 1];i--;j--;}else if (dp[i - 1][j] > dp[i][j - 1]){i--;}elsej--;}printf("最长公共子序列是: %s\n", lcs_str);for (int i = 0; i <= m; i++){free(dp[i]);}free(dp);free(lcs_str);
}int main()
{char a[] = "elo world!";char b[] = "welcome odl!";int m = strlen(a);int n = strlen(b);int result = maxleng(a, b, m, n);printf("最长公共子序列的长度是: %d\n", result);printchar(a, b, m, n);return 0;
}