最长公共子序列c语言
时间: 2023-07-02 22:24:00 浏览: 116
以下是求解两个字符串最长公共子序列的C语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *s1, char *s2) {
int len1 = strlen(s1);
int len2 = strlen(s2);
int dp[MAX_LEN][MAX_LEN];
// 初始化dp数组
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= len2; i++) {
dp[0][i] = 0;
}
// 填充dp数组
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1][len2];
}
int main() {
char s1[MAX_LEN], s2[MAX_LEN];
printf("请输入两个字符串:\n");
scanf("%s%s", s1, s2);
printf("最长公共子序列长度为:%d\n", lcs(s1, s2));
return 0;
}
```
在这个代码中,我们使用动态规划的思想来解决最长公共子序列问题,其中 `dp[i][j]` 表示 `s1` 中前 `i` 个字符与 `s2` 中前 `j` 个字符的最长公共子序列的长度。如果 `s1[i-1]` 等于 `s2[j-1]`,则说明这两个字符取自于最长公共子序列,因此 `dp[i][j]` 要加上 `dp[i-1][j-1]`;否则,如果这两个字符不相等,则说明它们不可能同时出现在最长公共子序列中,因此我们需要取 `dp[i-1][j]` 和 `dp[i][j-1]` 中的最大值作为 `dp[i][j]` 的值。最终, `dp[len1][len2]` 的值就是最长公共子序列的长度。