最长公共子序列穷举法c语言代码
时间: 2024-03-25 07:34:02 浏览: 21
最长公共子序列(Longest Common Subsequence,简称LCS)是指在两个序列中找到最长的公共子序列的问题。穷举法是一种解决LCS问题的方法之一,下面是一个用C语言实现的穷举法代码示例:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char* X, char* Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int main() {
char X[] = "ABCDEF";
char Y[] = "ABDCEF";
int m = strlen(X);
int n = strlen(Y);
printf("最长公共子序列的长度为:%d\n", lcs(X, Y, m, n));
return 0;
}
```
上述代码中,`lcs`函数用于计算最长公共子序列的长度。其中,`X`和`Y`分别表示两个序列,`m`和`n`分别表示两个序列的长度。通过递归的方式,不断比较序列中的字符,如果相等则长度加1,否则取两个序列分别去掉最后一个字符后的最长公共子序列的长度的较大值。最终返回的就是最长公共子序列的长度。