C语言穷举法实现最长公共子序列
时间: 2024-04-08 07:26:19 浏览: 14
C语言中可以使用穷举法(也称为暴力法)来实现最长公共子序列(Longest Common Subsequence,简称LCS)。穷举法是一种简单但效率较低的算法,它通过遍历所有可能的子序列来找到最长公共子序列。
以下是C语言中使用穷举法实现最长公共子序列的示例代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char* str1, char* str2, int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (str1[m - 1] == str2[n - 1]) {
return 1 + lcs(str1, str2, m - 1, n - 1);
} else {
return max(lcs(str1, str2, m, n - 1), lcs(str1, str2, m - 1, n));
}
}
int main() {
char str1[] = "ABCD";
char str2[] = "ACDF";
int m = strlen(str1);
int n = strlen(str2);
int result = lcs(str1, str2, m, n);
printf("最长公共子序列的长度为:%d\n", result);
return 0;
}
```
上述代码中,我们定义了一个递归函数`lcs`来计算最长公共子序列的长度。函数中使用了两个指针`m`和`n`来表示两个字符串的长度,通过比较字符是否相等来确定是否属于公共子序列。如果字符相等,则递归调用`lcs`函数,并将两个指针都向前移动一位;如果字符不相等,则分别递归调用`lcs`函数,一个指针向前移动一位,另一个指针保持不变。最后,返回两种情况中的较大值。
运行上述代码,将输出最长公共子序列的长度为3。