用C语言编写给你一个序列X和另一个序列Z,当Z中的所有元素都在X中存在,并且在X中的下标顺序是严格递增的,那么就把Z叫做X的子序列。 例如:Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>的一个子序列,Z中的元素在X中的下标序列为<1,2,4,6>。 现给你两个序列X和Y,请问它们的最长公共子序列的长度是多少?输入包含多组测试数据。每组输入占一行,为两个字符串,由若干个空格分隔。每个字符串的长度不超过100。对于每组输入,输出两个字符串的最长公共子序列的长度。
时间: 2024-03-09 07:48:43 浏览: 84
以下是使用动态规划算法求解最长公共子序列的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 *X, char *Y, int m, int n) {
int L[m + 1][n + 1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
L[i][j] = L[i - 1][j - 1] + 1;
} else {
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
}
return L[m][n];
}
int main() {
char X[MAX_LEN], Y[MAX_LEN];
while (scanf("%s%s", X, Y) == 2) {
int m = strlen(X);
int n = strlen(Y);
int len = lcs(X, Y, m, n);
printf("%d\n", len);
}
return 0;
}
```
在这个代码中,`lcs`函数用于计算两个字符串的最长公共子序列的长度。在主函数中,通过循环读入多组测试数据,并调用`lcs`函数求解最长公共子序列的长度,最后输出结果。
阅读全文