在javascript中如何實現最長公共子序列

最長公共子序列（longest common sequence）和最長公共子字串（longest common substring）不是一回事兒，下面這篇文章主要給大家介紹了關於javascript實現最長公共子序列的相關資料，需要的朋友可以參考下。

介紹

最長公共子序列（Longest Common Subsequence LCS）是從給定的兩個序列X和Y中取出盡可能多的一部分字符，按照它們在原序列排列的先後次序排列得到。 LCS問題的演算法用途廣泛，如在軟體不同版本的管理中，用LCS演算法找到新舊版本的異同處;在軟體測試中，用LCS演算法對錄製和回放的序列進行比較，在基因工程領域，用LCS演算法檢查病人DNA連與鍵康DNA鏈的異同;在防抄襲系統中，用LCS演算法檢查論文的抄襲率。 LCS演算法也可以用於程式碼相似度度量，人體運行的序列檢索，視頻段匹配等方面，所以對LCS演算法進行研究具有很高的應用價值。

基本概念

子序列(subsequence)： 一個特定序列的子序列就是將給定序列中零個或多個元素去掉後得到的結果(不改變元素間相對次序)。例如序列23195a5eab8013c21303d3d24e81fe27的子序列有：4e2154b1242725e74a11c55ea3967ed3、2cf3a2d5a55d4ffa7aceebabd439c436、46ebfb08a9464431c0e7a43662984975 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)。這就推出了與反正假設矛盾的結果。

得證。

我們現在用下面的方程式來繼續填表了。

程式實作

//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]
 }

LCS可以進一步簡化，只要透過挪位置，省去新陣列的產生

//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];
}

#列印一個LCS

我們再來給列印函數，先看如何列印一個。我們從右下角開始尋找，一直找到最上一行終止。因此目標字串的建構是倒序。為了避免使用stringBuffer這樣麻煩的中間量，我們可以透過遞歸實現，每次執行程式時，只傳回一個字串，沒有則傳回一個空字串， 以 printLCS(x,y,...) str[i ] 相加，就可以得到我們要求的字串。

我們再寫出一個方法，來驗證我們得到的字串是否真正的LCS字串。作為一個已經工作的人，不能寫的程式碼像在校生那樣，不做單元測試就放到線上讓別人踩坑。

//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

#列印全部LCS

##想法與上面差不多，我們注意一下，在LCS方法有一個Math.max取值，這其實是整合了三種情況，因此可以分叉出三個字串。我們的方法將傳回一個es6集合對象，方便自動去掉。然後每次都用新的集合合併舊的集合的字任串。

//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
}

危險的遞歸解法

#str1的一個子序列對應於下標序列{1, 2, …, m}的子序列，因此，str1共有${2^m}$個不同子序列（str2亦然，如${2^n}$），因此複雜度達到驚人的指數時間（${2^m * 2^ n}$）。

//警告，字符串的长度一大就会爆栈
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
  }
 }

上面是我整理給大家的，希望今後會對大家有幫助。

相關文章：

使用vue實作二級路由設定方法

#react專案開發

在Vue-Router2.X中實作多種路由實作#

以上是在javascript中如何實現最長公共子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！