C语言用穷举搜索法求最长公共子序列代码实现
时间: 2024-05-13 08:10:37 浏览: 131
C语言求最长公共子序列
C语言中使用穷举搜索法求最长公共子序列的代码实现如下:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
void lcs(char *str1, char *str2, int m, int n) {
int lcs_table[m + 1][n + 1];
int i, j;
// 构建动态规划表
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
lcs_table[i][j] = 0;
else if (str1[i - 1] == str2[j - 1])
lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1;
else
lcs_table[i][j] = max(lcs_table[i - 1][j], lcs_table[i][j - 1]);
}
}
// 获取最长公共子序列
int index = lcs_table[m][n];
char lcs_sequence[index + 1];
lcs_sequence[index] = '\0';
i = m;
j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs_sequence[index - 1] = str1[i - 1];
i--;
j--;
index--;
} else if (lcs_table[i - 1][j] > lcs_table[i][j - 1])
i--;
else
j--;
}
// 输出最长公共子序列
printf("最长公共子序列为:%s\n", lcs_sequence);
}
int main() {
char str1[] = "ABCBDAB";
char str2[] = "BDCAB";
int m = strlen(str1);
int n = strlen(str2);
lcs(str1, str2, m, n);
return 0;
}
```
阅读全文