LCS-最长公共子序列

概念：A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。

1）最简单的方法还是暴力解决，循环找出A与B的所有子序列，然后进行比对找出最长子序列
2）动态规划，首先给出递推式
LCS-最长公共子序列
首先解释递推式，针对序列Am<a1,a2,a3,a4,a5…am>Bn<b1,b2,b3…bn>，他们的最长公共子序列是Ck<c1,c2,c3…ck>,即存在以下两种情况

1）am = bn时，即am = bn = ck，即Ck-1是Am-1和Bn-1的最长公共子序列
2）am != bn时，此时Ck是Am-1和Bn或Am和Bn-1的最长公共子序列

根据以上两种情况，可以得出依据于长度的递推式。C[I,J]表示Ai和Bj的最长公共子序列的长度。即可写出上图所示递推式。

依据递推式可以列出长度表示表。

LCS-最长公共子序列
在后续递归找出最长公共子序列
js代码如下

// "1代表左上"
// "2代表上"
// "3代表左"

(function(){
  let A = "ACCGGTCGAGATGCAG".split("");
  let B = "GTCGTTCGGAATGCAT".split("");
  let LCS = "";

  A.unshift("");
  B.unshift("")

  var init = function(){
    let c = [];

    for(let i = 0; i < A.length; i++){
      c[i] = [];
      c[i].length = B.length;
      for(let j = 0; j < B.length; j++){
        if(i == 0){
          c[i][j] = {lcs: 0,source: 0};
        }
        if(j == 0 ){
          c[i][j] = {lcs: 0,source: 0};
        }
      }
    }

    return c;
  }
  // 构建表
  // 根据递归公式
  var build = function () {  
    let c = init();

    for(let i = 1; i < A.length; i++){
      for(let j = 1; j < B.length; j++){
        if(A[i] == B[j]){
          c[i][j] = {
            lcs: c[i - 1][j - 1].lcs + 1,
            source: 1
          };
        }else{
          if(c[i - 1][j].lcs > c[i][j - 1].lcs){
            c[i][j] = {
              lcs: c[i - 1][j].lcs,
              source: 2
            }
          }else{
            c[i][j] = {
              lcs: c[i][j - 1].lcs,
              source: 3
            }
          }
        }
      }
    }

    return c;
  }

  var lcs = function (c, x, i, j) {  
    if(i == 0 || j == 0){
      return
    }
    if(c[i][j].source == 1){
      LCS = x[i] + LCS;
      lcs(c, x, i - 1, j - 1);
    }else if(c[i][j].source == 2){
      lcs(c, x, i - 1, j);
    }else{
      lcs(c, x, i, j - 1);
    }
  }

  lcs(build(), A, A.length - 1, B.length - 1);

  console.log(LCS);
})()

LCS-最长公共子序列

相关推荐