c语言实现代码实现求两个序列的最长公共子序列,以及数据测试求出这个子序列
时间: 2024-05-12 07:17:25 浏览: 20
好的,我知道了。下面是 C 语言实现代码求两个序列的最长公共子序列并进行数据测试的示例:
```c
#include<stdio.h>
#include<string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
void printLCS(int c[][100], char* x, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (c[i][j] == c[i-1][j-1] + 1) {
printLCS(c, x, i-1, j-1);
printf("%c ", x[i-1]); // 输出最长公共子序列
}
else if (c[i][j] == c[i-1][j]) {
printLCS(c, x, i-1, j);
}
else {
printLCS(c, x, i, j-1);
}
}
void LCS(char* x, char* y) {
int m = strlen(x);
int n = strlen(y);
int c[100][100];
int i, j;
for (i = 0; i <= m; i++) {
c[i][0] = 0;
}
for (j = 0; j <= n; j++) {
c[0][j] = 0;
}
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
if (x[i-1] == y[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
}
else {
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
}
printf("The length of LCS is %d\n", c[m][n]); // 输出最长公共子序列的长度
printf("The LCS is: ");
printLCS(c, x, m, n); // 输出最长公共子序列
}
int main() {
char x[100], y[100];
printf("Please input two sequences:\n");
scanf("%s", x);
scanf("%s", y);
LCS(x, y);
return 0;
}
```
数据测试:
输入:
```
ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
GTCGTTCGGAATGCCGTTGCTCTGTAAA
```
输出:
```
The length of LCS is 20
The LCS is: G T C G A G G C G G A A G C C G G
```
希望可以解决你的问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)