算法代码
#include <stdio.h>
#include <stdlib.h>
const int N=10;
const int M=12;
int LCS_recursion(char A[],char B[],int i,int j)
{
if (i==0 || j==0)
return 0;
else
{
if (A[i]==B[j])
return LCS_recursion(A,B,i-1,j-1)+1;
else
return LCS_recursion(A,B,i,j-1)>LCS_recursion(A,B,i-1,j)
?LCS_recursion(A,B,i,j-1):LCS_recursion(A,B,i-1,j);
}
}
int LCS(char A[],char B[], int L[][M+1],int n,int m)
{
int i,j;
for(i=0;i<=n;i++)
L[i][0]=0;
for(j=0;j<=m;j++)
L[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(A[i]==B[j])
L[i][j]=L[i-1][j-1]+1;
else
L[i][j]=L[i][j-1]>L[i-1][j]?L[i][j-1]:L[i-1][j];
return L[n][m];
}
void table(char A[],char B[],int L[][M+1])
{
int i,j;
printf(" ");
for(i=1;i<=M;i++)
printf("%3c",B[i]);
printf("\n ");
for(i=0;i<=M;i++)
printf("%3d",i);
printf("\n ");
for(i=0;i<=M+1;i++)
printf("%3d",0);
printf("\n");
for(i=1;i<=N;i++)
{
printf("%c%3d",A[i],i);
for(j=0;j<=M;j++)
printf("%3d",L[i][j]);
printf("\n");
}
}
void main ()
{
char A[N+1]={'0','x','y','x','x','z','x','y','z','x','y'};
char B[M+1]={'0','z','x','z','y','y','z','x','x','y','x','x','z'};
int L[N+1][M+1];
long start,end;
LCS(A,B,L,N,M);
table(A,B,L);
printf("\nLCS : %d\n",L[N][M]);
printf("\nLCS_recursion : %d\n\n\n",LCS_recursion(A,B,N,M));
system("pause");
}
测试结果
![最长公共子序列 最长公共子序列](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzI1MS8wNDgwZmI1N2Y0YzMwZWRjMGI1OGQ0ZTlhMjdiMzVhYi5wbmc=)