C语言实现最长公共子序列算法

#include<stdio.h>

int CommonOrder(char x[],int m,char y[],int n,char z[]) { int i,j,k,L[m+1][n+1],S[m+1][n+1]; for(j=0;j<=n;j++) L[0][j]=0; for(i=0;i<=m;i++) L[i][0]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(x[i]==y[j]) { L[i][j]=L[i-1][j-1]+1;S[i][j]=1; } else if(L[i][j-1]>=L[i-1][j]) { L[i][j]=L[i][j-1];S[i][j]=2; } else{ L[i][j]=L[i-1][j];S[i][j]=3; } i=m;j=n;k=L[m][n]; while(i>0&&j>0) { if(S[i][j]==1){ z[--k]=x[i];--i;--j;} else if(S[i][j]==2) --j; else --i; } return L[m][n]; }

int main() { int m,n; printf("请输入X序列长度:"); scanf("%d",&m); printf("请输入Y序列长度:"); scanf("%d",&n); char x[m+1], y[n+1], z[m+n+1]; printf("X序列:"); scanf("%s",x); printf("Y序列:"); scanf("%s",y); int L[m+1][n+1]; int len=CommonOrder(x,m,y,n,z); printf("表中数据如下:\n"); for(int i=0;i<=m;i++) { for(int j=0;j<=n;j++) printf("%d ",L[i][j]); printf("\n"); } printf("最长公共子序列长度：%d\n",len); printf("最长公共子序列:"); for(int i=0;i<len;i++) printf("%c ",z[i]); return 0; }

// 修改说明： // 1. 在定义变量m和n后，定义数组L，保证数组L的维度正确。 // 2. 在输入x和y序列时，使用m和n限制输入长度，避免数组越界。 // 3. 在输出结果时，添加了注释说明程序的功能。

// 代码的功能： // 输入两个字符串x和y，计算它们的最长公共子序列，并输出最长公共子序列的长度和内容。

// 代码的优化建议： // 1. 可以使用更简洁的代码实现最长公共子序列算法。 // 2. 可以对代码进行更详细的注释，方便理解。 // 3. 可以增加一些错误处理机制，例如判断输入的字符串是否为空等。