用动态规划求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列,用c语言实现,打出代码
时间: 2023-11-23 11:11:03 浏览: 49
以下是用C语言实现求解最长公共子序列的代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
int LCS(char* str1, char* str2, int len1, int len2, int c[MAX_SIZE][MAX_SIZE], char b[MAX_SIZE][MAX_SIZE]) {
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i-1] == str2[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = '\\';
}
else if (c[i-1][j] >= c[i][j-1]) {
c[i][j] = c[i-1][j];
b[i][j] = '|';
}
else {
c[i][j] = c[i][j-1];
b[i][j] = '-';
}
}
}
return c[len1][len2];
}
void printLCS(char b[MAX_SIZE][MAX_SIZE], char* str1, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (b[i][j] == '\\') {
printLCS(b, str1, i-1, j-1);
printf("%c", str1[i-1]);
}
else if (b[i][j] == '|') {
printLCS(b, str1, i-1, j);
}
else {
printLCS(b, str1, i, j-1);
}
}
int main() {
char str1[] = "ABCDBAB";
char str2[] = "BDCABA";
int len1 = strlen(str1);
int len2 = strlen(str2);
int c[MAX_SIZE][MAX_SIZE] = {0};
char b[MAX_SIZE][MAX_SIZE] = {0};
int len = LCS(str1, str2, len1, len2, c, b);
printf("LCS is: ");
printLCS(b, str1, len1, len2);
printf("\n");
return 0;
}
```
输出结果为:
```
LCS is: BDAB
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)