写出c语言代码题目描述如下：我们称序列Z=z1z2zk是序列X=x1x2xm的子序列当且仅当存在严格上升的序列i1i2ik使得对j=12k有xij=zj。比如Z=abfc 是X=abcfbc的子序列。 现在给出两个序列X和Y你的任务是找到X和Y的最大公共子序列也就是说要找到一个最长的序列Z使得Z既是X的子序列也是Y的子序列。

#include <stdio.h> #include <string.h>

#define MAX_LEN 100

int LCS[MAX_LEN+1][MAX_LEN+1];

int max(int a, int b) { return a > b ? a : b; }

int lcs(char* X, char* Y, int m, int n) { for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { LCS[i][j] = 0; } else if (X[i-1] == Y[j-1]) { LCS[i][j] = LCS[i-1][j-1] + 1; } else { LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]); } } } return LCS[m][n]; }

int main() { char X[MAX_LEN], Y[MAX_LEN]; printf("请输入序列X："); scanf("%s", X); printf("请输入序列Y："); scanf("%s", Y); int m = strlen(X); int n = strlen(Y); int len = lcs(X, Y, m, n); printf("X和Y的最大公共子序列长度为：%d\n", len); return 0;