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]; int L[m+1][n+1]; printf("X序列:"); scanf("%s",x+1); printf("Y序列:"); scanf("%s",y+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]); z[len] = '\0'; // 添加字符串结束符 return 0; }