最长公共子序列问题。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},用动态规划算法找出X和Y的最长公共子序列,用C/C++实现该算法。
时间: 2024-05-10 15:14:22 浏览: 9
下面是C语言实现代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100
int max(int a, int b) {
return a > b ? a : b;
}
void lcs(char X[], char Y[], int m, int n, int L[][MAX_LENGTH]) {
int i, j;
// 填充L[m+1][n+1]数组
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i-1] == Y[j-1]) {
L[i][j] = L[i-1][j-1] + 1;
} else {
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
}
// 输出最长公共子序列
int index = L[m][n];
char result[index+1];
result[index] = '\0'; // 字符串末尾添加'\0'
i = m, j = n;
while (i > 0 && j > 0) {
if (X[i-1] == Y[j-1]) {
result[index-1] = X[i-1];
i--;
j--;
index--;
} else if (L[i-1][j] > L[i][j-1]) {
i--;
} else {
j--;
}
}
printf("最长公共子序列为: %s\n", result);
}
int main() {
char X[] = "ABCBDAB";
char Y[] = "BDCABA";
int m = strlen(X);
int n = strlen(Y);
int L[MAX_LENGTH][MAX_LENGTH];
lcs(X, Y, m, n, L);
return 0;
}
```
运行结果为:
```
最长公共子序列为: BCBA
```