assuming i,j start from 1;
0, ( i=0 or j=0)
c(i,j)= c(i-1,j-1)+1 ( i,j>0 and A[i]=B[j])
Max( c[i-1,j),c(i,j-1)) ( i,j>0 and A[i]!=B[j])
时间复杂度O(m*n),空间复杂度O(m*n)
#define MAX 100 int C[MAX][MAX]; int D[MAX][MAX]; //输出子序列 void Print_LCSub(char *str,int i,int j){ if(i==0|| j==0) return; if(D[i][j]==0){ Print_LCSub(str,i-1,j-1); cout<<str[i-1]; } else if(D[i][j]==1) Print_LCSub(str,i-1,j); else Print_LCSub(str,i,j-1); } void LCSubsequence(char *str1,char *str2){ int len1,len2; int i,j; len1=strlen(str1); len2=strlen(str2); for(i=0;i<=len1;i++) C[i][0]=0; for(j=1;j<=len2;j++) C[0][j]=0; for(i=1;i<=len1;i++){ for(j=1;j<=len2;j++){ if(str1[i-1]==str2[j-1]){ C[i][j]=C[i-1][j-1]+1; D[i][j]=0; // left and up } else if(C[i-1][j]>=C[i][j-1]){ C[i][j]=C[i-1][j]; D[i][j]=1; // up } else { C[i][j]=C[i][j-1]; D[i][j]=-1; // left } } } //output matrix for(i=0;i<=len1;i++){ for(j=0;j<=len2;j++) cout<<setw(2)<<C[i][j]<<" "; cout<<endl; } cout<<"MaxLen="<<C[len1][len2]<<endl; Print_LCSub(str1,len1,len2); cout<<endl; } void main(){ char str1[200]="xab4c3de89fgh"; char str2[200]="ac234egxxh9"; //freopen("D:/test.txt","r",stdin); LCSubsequence(str1,str2); }
输出结果: