詳談javascript最長公共子序列

假设有两个数组，A和B。A[i]为A的第i个元素，A(i)为由A的第一个元素到第i个元素所组成的前缀。m(i, j)为A(i)和B(j)的最长公共子序列长度。

由于算法本身的递推性质，其实只要证明，对于某个i和j：

  m(i, j) = m(i-1, j-1) + 1 （当A[i] = B[j]时）

  m(i, j) = max( m(i-1, j), m(i, j-1) ) （当A[i] != B[j]时）

第一个式子很好证明，即当A[i] = B[j]时。可以用反证，假设m(i, j) > m(i-1, j-1) + 1 （m(i, j)不可能小于m(i-1, j-1) + 1，原因很明显），那么可以推出m(i-1, j-1)不是最长的这一矛盾结果。

第二个有些trick。当A[i] != B[j]时，还是反证，假设m(i, j) > max( m(i-1, j), m(i, j-1) )。

由反证假设，可得m(i, j) > m(i-1, j)。这个可以推出A[i]一定在m(i, j)对应的LCS序列中（反证可得）。而由于A[i] != B[j]，故B[j]一定不在m(i, j)对应的LCS序列中。所以可推出m(i, j) = m(i, j-1)。这就推出了与反正假设矛盾的结果。

得证。</p>
<p> </p>
<p>我們現在用下面的方程式來繼續填表了。 </p>
<p><img  src="https://img.php.cn/upload/article/000/054/025/4261b59f87cbe8cff3afd0492985a179-3.png" alt="詳談javascript最長公共子序列" ></p>
<h2>程式實現</h2>
<pre class="brush:php;toolbar:false">//by 司徒正美
function LCS(str1, str2){
        var rows =  str1.split("")
        rows.unshift("")
        var cols =  str2.split("")
        cols.unshift("")
        var m = rows.length 
        var n = cols.length 
        var dp = []
        for(var i = 0; i < m; i++){ 
            dp[i] = []
            for(var j = 0; j < n; j++){ 
                if(i === 0 || j === 0){
                    dp[i][j] = 0
                    continue
                }
              
                if(rows[i] === cols[j]){ 
                    dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
                }else{
                    dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //对左边，上边取最大
                }
            }
            console.log(dp[i].join(""))//调试
        } 
        return dp[i-1][j-1]
    }

//by司徒正美
function LCS(str1, str2){
    var m = str1.length 
    var n = str2.length
    var dp = [new Array(n+1).fill(0)] //第一行全是0
    for(var i = 1; i <= m; i++){ //一共有m+1行
        dp[i] = [0] //第一列全是0
        for(var j = 1; j <= n; j++){//一共有n+1列
            if(str1[i-1] === str2[j-1]){ 
                //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
                dp[i][j] = dp[i-1][j-1] + 1 //对角＋1
            } else {
                 dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
            }
        }
    } 
    return dp[m][n];
}

//by 司徒正美，打印一个LCS
function printLCS(dp, str1, str2, i, j){
    if (i == 0 || j == 0){
        return "";
    }
    if( str1[i-1] == str2[j-1] ){
        return printLCS(dp, str1, str2, i-1, j-1) + str1[i-1];
    }else{
        if (dp[i][j-1] > dp[i-1][j]){
            return printLCS(dp, str1, str2, i, j-1);
        }else{
            return printLCS(dp, str1, str2, i-1, j);
        }
    }
}
//by司徒正美， 将目标字符串转换成正则，验证是否为之前两个字符串的LCS
function validateLCS(el, str1, str2){
   var re =  new RegExp( el.split("").join(".*") )
   console.log(el, re.test(str1),re.test(str2))
   return re.test(str1) && re.test(str2)
}

function LCS(str1, str2){
    var m = str1.length 
    var n = str2.length
    //....略，自行补充
    var s = printLCS(dp, str1, str2, m, n)
    validateLCS(s, str1, str2)
    return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

//by 司徒正美 打印所有LCS
function printAllLCS(dp, str1, str2, i, j){
    if (i == 0 || j == 0){
        return new Set([""])
    }else if(str1[i-1] == str2[j-1]){
        var newSet = new Set()
        printAllLCS(dp, str1, str2, i-1, j-1).forEach(function(el){
            newSet.add(el + str1[i-1])
        })
        return newSet
    }else{
        var set = new Set()
        if (dp[i][j-1] >= dp[i-1][j]){
            printAllLCS(dp, str1, str2, i, j-1).forEach(function(el){
              set.add(el)
            })
        }
        if (dp[i-1][j] >= dp[i][j-1]){//必须用>=，不能简单一个else搞定
            printAllLCS(dp, str1, str2, i-1, j).forEach(function(el){
              set.add(el)
            })
        }   
        return set
    } 
 }

function LCS(str1, str2){
    var m = str1.length 
    var n = str2.length
    //....略，自行补充
    var s =  printAllLCS(dp, str1, str2, m, n)
    console.log(s)
    s.forEach(function(el){
        validateLCS(el,str1, str2)
        console.log("输出LCS",el)
    })
    return dp[m][n]
}
var c1 = LCS( "ABCBDAB","BDCABA");
console.log(c1) //4 BCBA、BCAB、BDAB
var c2 = LCS("13456778" , "357486782" );
console.log(c2) //5 34678 
var c3 = LCS("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA" ,"GTCGTTCGGAATGCCGTTGCTCTGTAAA" );
console.log(c3) //20 GTCGTCGGAAGCCGGCCGAA

function LCS(str1, str2){
    var m = str1.length 
    var n = str2.length
    var dp = [new Array(n+1).fill(0)],now = 1，row //第一行全是0
    for(var i = 1; i <= m; i++){ //一共有2行
        row = dp[now] = [0] //第一列全是0
        for(var j = 1; j <= n; j++){//一共有n+1列
            if(str1[i-1] === str2[j-1]){ 
                //注意这里，str1的第一个字符是在第二列中，因此要减1，str2同理
                dp[now][j] = dp[i-now][j-1] + 1 //对角＋1
            } else {
                dp[now][j] = Math.max( dp[i-now][j], dp[now][j-1]) 
            }
        }
        now = 1- now; //1-1=>0;1-0=>1; 1-1=>0 ...
    } 
    return row ? row[n]: 0
}

//警告，字符串的长度一大就会爆栈
function LCS(str1, str2, a, b) {
      if(a === void 0){
          a = str1.length - 1
      }
      if(b === void 0){
          b = str2.length - 1
      }
      if(a == -1 || b == -1){
          return 0
      } 
      if(str1[a] == str2[b]) {
         return LCS(str1, str2,  a-1, b-1)+1;
      }
      if(str1[a] != str2[b]) {
         var x =  LCS(str1, str2, a, b-1)
         var y =  LCS(str1, str2, a-1, b)
         return x >= y ? x : y
      }
  }