最长公共子序列动态规划算法C语言实现
时间: 2023-11-25 12:48:35 浏览: 106
以下是C语言实现最长公共子序列动态规划算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 100
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] = 1;
} else if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 2;
} else {
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
}
return c[len1][len2];
}
void print_lcs(int **b, char *str, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (b[i][j] == 1) {
print_lcs(b, str, i - 1, j - 1);
printf("%c", str[i - 1]);
} else if (b[i][j] == 2) {
print_lcs(b, str, i - 1, j);
} else {
print_lcs(b, str, i, j - 1);
}
}
int main() {
char str1[MAXLEN], str2[MAXLEN];
int **c, **b;
int len;
printf("请输入第一个字符串:");
scanf("%s", str1);
printf("请输入第二个字符串:");
scanf("%s", str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
c = (int **) malloc((len1 + 1) * sizeof(int *));
b = (int **) malloc((len1 + 1) * sizeof(int *));
for (int i = 0; i <= len1; i++) {
c[i] = (int *) malloc((len2 + 1) * sizeof(int));
b[i] = (int *) malloc((len2 + 1) * sizeof(int));
}
len = lcs_length(str1, str2, c, b);
printf("最长公共子序列长度为:%d\n", len);
printf("最长公共子序列为:");
print_lcs(b, str1, len1, len2);
printf("\n");
for (int i = 0; i <= len1; i++) {
free(c[i]);
free(b[i]);
}
free(c);
free(b);
return 0;
}
```
阅读全文