lcs最大公共子序列问题

读算法导论
第四部分第15章，提到DNA解析的时候的最大公共子序列问题。按书上描述用js实现代码如下

var str1 = 'accggtcgagtgcgcggaagccggccgaa';
var str2 = 'gtcgttcggaatgccgttgctctgtaaa';
var rl = new Array();
function LCS(str1,str2){
  var m = str1.length ;
  var n = str2.length ;
  //模拟二维数组
  //var rl = new Array();
  for(var i=0;i<=m;i++){
     rl[i] = new Array();
for(var j=0;j<=n;j++){
   rl[i][j] = -1 ; //初始化
}
  }

  for(i=0;i<=m;i++){
    rl[i][0] = 0 ;
  }
  for(j=0;j<=n;j++){
    rl[0][j] = 0 ;
  }
  //初始化
  for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
   if(str1.charAt(i-1)==str2.charAt(j-1)){
      rl[i][j] =rl[i-1][j-1] + 1 ;
   }else{
      rl[i][j] = Math.max(rl[i-1][j],rl[i][j-1]);
   }
}
  }
  //return rl[m][n];
}
LCS(str1,str2); //执行求出 最大公共子序列的长度。



function printLCS(str1,str2){
       var m = str1.length ;
var n = str2.length;
if(m*n==0){
  return '';
}
if(str1.charAt(m-1)==str2.charAt(n-1)){
return  printLCS(str1.substring(0,m-1),str2.substring(0,n-1)) +str1.charAt(m-1) ;
  
}else {
    if(rl[m-1][n]>rl[m][n-1]){
    return  printLCS(str1.substring(0,m-1),str2);
}else {
   return printLCS(str1,str2.substring(0,n-1));
}
}

} //递归求出lsc

printLCS(str1,str2); //求出最大公共子序列