长公共子序列问题(00001).doc

#include#include#define N 20void 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<=m;i++)c[i][0]=0; for (i=1;i<=n;i++)c[0][i]=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]='A';}else if (c[i-1][j]>=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);}
2. 最长公共子序列问题-c实现
动态规划的经典应用,其实现在发现,其实质就是利用矩阵或者数组保存历史结果,而不用每次递归求解
关键点:

,直接转化为矩阵上的数据运算
本问题的递归表达式为:
L[i,j]等于 0      ifi=0 或者 j=0
              等于L[i-1,j-1]+1   ifi>0 ,j>0 ai = bi
              等于 max{L[i,j-1], L[i-1,j]} if i > 0 j>0, ai != bj
纯c实现
 1 #include <>
 2 #include <>
 3 #define MAXSIZE 10
 4 static char * LCSarray;
 5 static char *start; //指向LCSarray数组中最长公共字串的开始位置
 6 int findLCS(char*, int,  char*, int );
 7 
 8 int main()
 9 {
10     char * a = "0xyxxzxyzxy";  //第一位都没有意义