#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100
// 动态规划数组
int dp[MAX_LENGTH + 1][MAX_LENGTH + 1];
// 计算两个字符串的最长公共子序列
void findLCS(char str1[], char str2[]) {
int len1 = strlen(str1);
int len2 = strlen(str2);
// 初始化动态规划数组
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (str1[i - 1] == str2[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];
}
}
// 输出最长公共子序列的长度
printf("长度: %d\n", dp[len1][len2]);
// 输出最长公共子序列
int index = dp[len1][len2];
char lcs[index + 1];
lcs[index] = '\0'; // 结尾字符
int i = len1, j = len2;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs[index - 1] = str1[i - 1];
i--;
j--;
index--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
// 输出最长公共子序列
printf("子序列: %s\n", lcs);
}
int main() {
char str1[] = "ABCBDAB";
char str2[] = "BDCAB";
findLCS(str1, str2);
char str3[] = "AB";
findLCS(str1, str3);
char str4[] = "ABB";
findLCS(str1, str4);
return 0;
}