最长公共子序列.（C语言编写） 算法

#include<iostream.h> #include<string.h> #define N 50 void LCSLength(char x[N+1],char y[N+1],int B[N+1][N+1]); void LCS(int i,int j,char x[N+1],int B[N+1][N+1]); void main() { char x[N+1],y[N+1];int B[N+1][N+1];int lx,ly; printf("请依次输入序列X的元素和序列Y的元素，按空格或者回车键结束输入\n"); scanf("%s",x+1); //从x[1]开始输入数据 scanf("%s",y+1);//从y[1]开始输入数据 lx=strlen(x+1); ly=strlen(y+1); printf("LCS的最长公共子序列的长度是 "); LCSLength(x,y,B); printf("\n"); printf("LCS的最长公共子序列是 "); LCS(lx,ly,x,B); printf("\n"); } void LCSLength(char x[],char y[],int B[N+1][N+1]) { int i,j,m,n; int C[N+1][N+1]; //C[i][j]表示记录序列{x1,x2,……xi}与序列{y1,y2,……yj}的最长公共子序列元素的个数 m=strlen(x+1); n=strlen(y+1); for(i=1;i<=m;i++) { C[i][0]=0; } for(j=1;j<=n;j++) C[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) { if(x[i]==y[j]) { C[i][j]=C[i-1][j-1]+1; B[i][j]=1; } else if(C[i][j-1]>C[i-1][j]) { C[i][j]=C[i][j-1]; B[i][j]=2; } else { C[i][j]=C[i-1][j]; B[i][j]=3; } } printf("%d",C[m][n]); } void LCS(int i,int j,char x[],int B[N+1][N+1]) { if(i==0||j==0) return; if(B[i][j]==1) { LCS(i-1,j-1,x,B); printf("%c",x[i]); } else if(B[i][j]==2) { LCS(i,j-1,x,B); } else { LCS(i-1,j,x,B); } }