写一个c语言代码每组数据两行字符串,由小写英文字母表示,每个字符长度小于100输出最长公共子序列。如果没有公共序列,输出“NO”。
时间: 2024-05-14 11:16:51 浏览: 14
好的,这是一个比较经典的动态规划问题,我来为你提供代码:
```c
#include <stdio.h>
#include <string.h>
#define MAXLEN 100
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *str1, char *str2, int m, int n) {
int dp[MAXLEN + 1][MAXLEN + 1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (str1[i-1] == str2[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[m][n];
}
int main() {
char str1[MAXLEN + 1];
char str2[MAXLEN + 1];
while (scanf("%s%s", str1, str2) == 2) {
int m = strlen(str1);
int n = strlen(str2);
int ans = lcs(str1, str2, m, n);
if (ans == 0) {
printf("NO\n");
} else {
printf("%d\n", ans);
}
}
return 0;
}
```
这段代码实现了最长公共子序列问题的动态规划解法,时间复杂度为 O(mn),其中 m 和 n 分别是两个字符串的长度。需要注意的是,我们在输入两个字符串时使用了 `scanf` 函数,这个函数会依次将输入流中的内容按格式转换并赋值给指定的变量。多组数据时,只要输入的行数符合格式要求,就能够正确地读入数据。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)