最长公共子序列算法C语言实现（源程序）

#include

#include

#define N 20

void LCSLength(int m,int n,char x[N+1],char y[N+1],char b[N+1][N+1]);

void LCS(int i,int j,char x[N+1],char b[N+1][N+1]);

void main()

{

int lx,ly;

char X[N+1],Y[N+1];

int B[N+1][N+1];

scanf("%s",X+1);

scanf("%s",Y+1);

lx=strlen(X+1);

ly=strlen(Y+1);

LCSLength(lx,ly,X,Y,B);

LCS(lx,ly,X,B);

}

/* Functions */

void LCSLength(int m,int n,char x[],char y[],char b[N+1][N+1])

{

int i,j;

int c[N+1][N+1];

for (i=1;i=c[i][j-1])

{

c[i][j]=c[i-1][j];

b[i][j]='U';

}

else

{

c[i][j]=c[i][j-1];

b[i][j]='L';

}

}

}

void LCS(int i,int j,char x[],char b[N+1][N+1])

{

if (i==0 || j==0)

return;

if (b[i][j]=='A')

{

LCS(i-1,j-1,x,b);

printf("%c",x[i]);

}

else if (b[i][j]=='U')

LCS(i-1,j,x,b);

else LCS(i,j-1,x,b);

}