最长公共子序列 - JAVA

给定两个序列X= 和Y= ,求X和Y长度最长的公共子序列。

可以用动态规划的方法解决这个问题,建立数组c[i][j]，i和j分别表示X_i和Y_j的的LCS长度，如果i=0,j=0,c[i][j]=0,根据最优子结构的性质，得到问题的递推公式为：

建立数组b[i][j]，如果b[i][j]=0,代表c[i][j]=c[i-1][j-1]+1的情况，如果b[i][j]=-1,代表c[i][j]=c[i][j-1]的情况，如果b[i][j]=1,代表c[i][j]=c[i-1][j]的情况。数组b[i][j]在递归地构造LCS时会用到。

程序为：< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;"># include # include # include # define N 100 int main() { int f1(char *a,char *b,int c[][N],int d[][N]); void print(int b[][N],char *a,int i,int j); char a[20]="abcrty"; char b[20]="aerbtyc"; int c[N][N]; int d[N][N]; int i,j; char *s=0; f1(a,b,c,d); print(d,a,strlen(a),strlen(b)); system("pause"); return 0; } int f1(char *a,char *b,int c[][N],int d[][N]) { int lena=strlen(a); int lenb=strlen(b); int i=0; int j=0; for(i=0;i<=lena;i++) //c[i][j]的初始化 c[i][0]=0; for(j=0;j<=lenb;j++) c[0][j]=0; for(i=1;i<=lena;i++) //递推公式 for(j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]){ c[i][j]=c[i-1][j-1]+1; d[i][j]=0; } else if(c[i-1][j]>c[i][j-1]){ c[i][j]=c[i-1][j]; d[i][j]=1; } else { c[i][j]=c[i][j-1]; d[i][j]=-1; } } return 0; } void print(int b[][N],char *a,int i,int j) //递归的方法构造LCS { if(i==0||j==0) return ; if(b[i][j]==0){ print(b,a,i-1,j-1); printf("%c\t",a[i-1]); } else if (b[i][j]==1) print(b,a,i-1,j); else print(b,a,i,j-1); }

上面的代码使用了附加空间b数组，在构造LCS时采用了递归，因为程序的效率较低，对上面的代码稍作优化，不使用数组b,构造用循环的方式构造LCS。代码如下：

# include 
  
   
# include 
   
     # include 
    
      # define N 100 int main() { int f(char *a,char *b,int c[][N]); char * lcs(char s[],char *a,char *b,int c[][N]); char a[20]="abcrty"; char b[20]="aerbtyc"; int c[N][N]; int d[N][N]; int i,j; char *s=0; f(a,b,c); s=lcs(s,a,b,c); printf("%s\n",s); system("pause"); return 0; } int f(char *a,char *b,int c[][N]) { int lena=strlen(a); int lenb=strlen(b); int i=0,j=0; for(i=0;i<=lena;i++) //初始化 c[i][0]=0; for(j=0;j<=lenb;j++) c[0][j]=0; for(i=1;i<=lena;i++) //递推公式 for(j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; } return c[lena][lenb]; } char * lcs(char s[],char *a,char *b,int c[][N]) { int i=strlen(a); int j=strlen(b); int k=f(a,b,c); s=(char *)malloc(k*sizeof(char)); s[k]='\0'; while(k>0) { if(c[i][j]==c[i-1][j]) i--; else if(c[i][j]==c[i][j-1]) j--; else { s[--k]=a[i-1]; i--;j--; } } return s; //最长公共子序列 }