介紹

最長(zhǎng)公共子序列（Longest Common Subsequence LCS）是從給定的兩個(gè)序列X和Y中取出盡可能多的一部分字符，按照它們?cè)谠蛄信帕械南群蟠涡蚺帕械玫健CS問(wèn)題的算法用途廣泛，如在軟件不同版本的管理中，用LCS算法找到新舊版本的異同處;在軟件測(cè)試中，用LCS算法對(duì)錄制和回放的序列進(jìn)行比較，在基因工程領(lǐng)域，用LCS算法檢查患者DNA連與鍵康DNA鏈的異同;在防抄襲系統(tǒng)中，用LCS算法檢查論文的抄襲率。LCS算法也可以用于程序代碼相似度度量，人體運(yùn)行的序列檢索，視頻段匹配等方面，所以對(duì)LCS算法進(jìn)行研究具有很高的應(yīng)用價(jià)值。

基本概念

子序列(subsequence)： 一個(gè)特定序列的子序列就是將給定序列中零個(gè)或多個(gè)元素去掉后得到的結(jié)果(不改變?cè)亻g相對(duì)次序)。例如序列<A,B,C,B,D,A,B>的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。

公共子序列(common subsequence)： 給定序列X和Y，序列Z是X的子序列，也是Y的子序列，則Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]為X和Y的公共子序列，其長(zhǎng)度為3。但Z不是X和Y的最長(zhǎng)公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均為X和Y的最長(zhǎng)公共子序列，長(zhǎng)度為4，而X和Y不存在長(zhǎng)度大于等于5的公共子序列。對(duì)于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。

最長(zhǎng)公共子序列：給定序列X和Y，從它們的所有公共子序列中選出長(zhǎng)度最長(zhǎng)的那一個(gè)或幾個(gè)。
子串： 將一個(gè)序列從最前或最后或同時(shí)刪掉零個(gè)或幾個(gè)字符構(gòu)成的新系列。區(qū)別與子序列，子序列是可以從中間摳掉字符的。cnblogs這個(gè)字符串中子序列有多少個(gè)呢？很顯然有27個(gè)，比如其中的cb,cgs等等都是其子序列

給一個(gè)圖再解釋一下：

我們可以看出子序列不見(jiàn)得一定是連續(xù)的，連續(xù)的是子串。

問(wèn)題分析

我們還是從一個(gè)矩陣開(kāi)始分析,自己推導(dǎo)出狀態(tài)遷移方程。

首先，我們把問(wèn)題轉(zhuǎn)換成前端夠?yàn)槭煜さ母拍睿灰蛄行蛄械亟辛?，可以認(rèn)為是數(shù)組或字符串。一切從簡(jiǎn)，我們就估且認(rèn)定是兩個(gè)字符串做比較吧。

我們重點(diǎn)留意”子序列“的概念，它可以刪掉多個(gè)或零個(gè)，也可以全部干掉。這時(shí)我們的第一個(gè)子序列為 空字符串 （如果我們的序列不是字符串，我們還可以 ）！這個(gè)真是千萬(wàn)要注意到！許多人就是看不懂《算法導(dǎo)論》的那個(gè)圖表，還有許多博客的作者不懂裝懂。我們總是從左到右比較，當(dāng)然了第一個(gè)字符串，由于作為矩陣的高，就垂直放置了。

假令X ＝ "ABCDAB"， Y＝"BDCABA"，各自取出最短的序列，也就是空字符串與空字符串比較。LCS的方程解為一個(gè)數(shù)字，那么這個(gè)表格也只能填數(shù)字。兩個(gè)空字符串的公同區(qū)域的長(zhǎng)度為0.

然后我們X不動(dòng)，繼續(xù)讓空字符串出陣，Y讓“B”出陣，很顯然，它們的公共區(qū)域的長(zhǎng)度為0. Y換成其他字符， D啊，C啊， 或者， 它們的連續(xù)組合DC、 DDC， 情況沒(méi)有變， 依然為0. 因此第一行都為0. 然后我們Y不動(dòng)，Y只出空字任串，那么與上面的分析一樣，都為0，第一列都是0.

LCS問(wèn)題與背包問(wèn)題有點(diǎn)不一樣，背包問(wèn)題還可以設(shè)置-1行，而最長(zhǎng)公共子序列因?yàn)橛锌兆有蛄械某霈F(xiàn)，一開(kāi)始就把左邊與上邊固定死了。

然后我們?cè)賹?wèn)題放大些，這次雙方都出一個(gè)字符，顯然只有兩都相同時(shí)，才有存在不為空字符串的公共子序列，長(zhǎng)度也理解數(shù)然為1。

A為"X", Y為"BDCA"的子序列的任意一個(gè)

繼續(xù)往右填空，該怎么填？顯然，LCS不能大于X的長(zhǎng)度，Y的從A字符串開(kāi)始的子序列與B的A序列相比，怎么也能等于1。

如果X只從派出前面?zhèn)€字符A,B吧，亦即是“”，“A”, "B", "AB"這四種組合，前兩個(gè)已經(jīng)解說(shuō)過(guò)了。那我們先看B，${X_1} == ${Y_0}， 我們得到一個(gè)新的公共子串了，應(yīng)該加1。為什么呢？因?yàn)槲覀冞@個(gè)矩陣是一個(gè)狀態(tài)表，從左到右，從上到下描述狀態(tài)的遷移過(guò)程，并且這些狀態(tài)是基于已有狀態(tài) 累加 出來(lái)的。 現(xiàn)在我們需要確認(rèn)的是，現(xiàn)在我們要填的這個(gè)格子的值與它周圍已經(jīng)填好的格子的值是存在何種關(guān)系 。目前，信息太少，就是一個(gè)孤點(diǎn)，直接填1。

然后我們讓Y多出一個(gè)D做幫手，{"",A,B,AB} vs {"",B,D,BD}，顯然，繼續(xù)填1. 一直填到Y(jié)的第二個(gè)B之前，都是1。 因?yàn)榈紹DCAB時(shí)，它們有另一個(gè)公共子序列，AB。

到這一步，我們可以總結(jié)一些規(guī)則了，之后就是通過(guò)計(jì)算驗(yàn)證我們的想法，加入新的規(guī)則或限定條件來(lái)完善。

Y將所有字符派上去，X依然是2個(gè)字符，經(jīng)仔細(xì)觀察，還是填2.

看五行，X再多派一個(gè)C，ABC的子序列集合比AB的子序列集合大一些，那么它與Y的B子序列集合大一些，就算不大，就不能比原來(lái)的小。顯然新增的C不能成為戰(zhàn)力，不是兩者的公共字符，因此值應(yīng)該等于AB的子序列集合。

并且我們可以確定，如果兩個(gè)字符串要比較的字符不一樣，那么要填的格子是與其左邊或上邊有關(guān)，那邊大就取那個(gè)。

如果比較的字符一樣呢，稍安毋躁，剛好X的C要與Y的C進(jìn)行比較，即ABC的子序列集合{"",A,B,C,AB,BC,ABC}與BDC的子序列集合｛"",B,D,C,BD,DC,BDC｝比較，得到公共子串有“”,B,D 。這時(shí)還是與之前的結(jié)論一樣，當(dāng)字符相等時(shí)，它對(duì)應(yīng)的格子值等于左邊與右邊與左上角的值，并且左邊，上邊，左上邊總是相等的。這些奧秘需要更嚴(yán)格的數(shù)學(xué)知識(shí)來(lái)論證。

假設(shè)有兩個(gè)數(shù)組，A和B。A[i]為A的第i個(gè)元素，A(i)為由A的第一個(gè)元素到第i個(gè)元素所組成的前綴。m(i, j)為A(i)和B(j)的最長(zhǎng)公共子序列長(zhǎng)度。

由于算法本身的遞推性質(zhì)，其實(shí)只要證明，對(duì)于某個(gè)i和j：

  m(i, j) = m(i-1, j-1) + 1 （當(dāng)A[i] = B[j]時(shí)）

  m(i, j) = max( m(i-1, j), m(i, j-1) ) （當(dāng)A[i] != B[j]時(shí)）

第一個(gè)式子很好證明，即當(dāng)A[i] = B[j]時(shí)?？梢杂梅醋C，假設(shè)m(i, j) > m(i-1, j-1) + 1 （m(i, j)不可能小于m(i-1, j-1) + 1，原因很明顯），那么可以推出m(i-1, j-1)不是最長(zhǎng)的這一矛盾結(jié)果。

第二個(gè)有些trick。當(dāng)A[i] != B[j]時(shí)，還是反證，假設(shè)m(i, j) > max( m(i-1, j), m(i, j-1) )。

由反證假設(shè)，可得m(i, j) > m(i-1, j)。這個(gè)可以推出A[i]一定在m(i, j)對(duì)應(yīng)的LCS序列中（反證可得）。而由于A[i] != B[j]，故B[j]一定不在m(i, j)對(duì)應(yīng)的LCS序列中。所以可推出m(i, j) = m(i, j-1)。這就推出了與反正假設(shè)矛盾的結(jié)果。

得證。

我們現(xiàn)在用下面的方程來(lái)繼續(xù)填表了。

程序?qū)崿F(xiàn)

//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 //對(duì)角＋1
    }else{
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) //對(duì)左邊，上邊取最大
    }
   }
   console.log(dp[i].join(""))//調(diào)試
  } 
  return dp[i-1][j-1]
 }

LCS可以進(jìn)一步簡(jiǎn)化，只要通過(guò)挪位置，省去新數(shù)組的生成

//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的第一個(gè)字符是在第二列中，因此要減1，str2同理
    dp[i][j] = dp[i-1][j-1] + 1 //對(duì)角＋1
   } else {
     dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1]) 
   }
  }
 } 
 return dp[m][n];
}

打印一個(gè)LCS

我們?cè)俳o出打印函數(shù)，先看如何打印一個(gè)。我們從右下角開(kāi)始尋找，一直找到最上一行終止。因此目標(biāo)字符串的構(gòu)建是倒序。為了避免使用stringBuffer這樣麻煩的中間量，我們可以通過(guò)遞歸實(shí)現(xiàn)，每次執(zhí)行程序時(shí)，只返回一個(gè)字符串，沒(méi)有則返回一個(gè)空字符串， 以 printLCS(x,y,...) + str[i] 相加，就可以得到我們要求的字符串。

我們?cè)賹?xiě)出一個(gè)方法，來(lái)驗(yàn)證我們得到的字符串是否真正的LCS字符串。作為一個(gè)已經(jīng)工作的人，不能寫(xiě)的代碼像在校生那樣，不做單元測(cè)試就放到線上讓別人踩坑。

//by 司徒正美，打印一個(gè)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司徒正美， 將目標(biāo)字符串轉(zhuǎn)換成正則，驗(yàn)證是否為之前兩個(gè)字符串的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
 //....略，自行補(bǔ)充
 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方法有一個(gè)Math.max取值，這其實(shí)是整合了三種情況，因此可以分叉出三個(gè)字符串。我們的方法將返回一個(gè)es6集合對(duì)象，方便自動(dòng)去掉。然后每次都用新的集合合并舊的集合的字任串。

//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]){//必須用>=，不能簡(jiǎn)單一個(gè)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
 //....略，自行補(bǔ)充
 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

空間優(yōu)化

使用滾動(dòng)數(shù)組：

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的第一個(gè)字符是在第二列中，因此要減1，str2同理
    dp[now][j] = dp[i-now][j-1] + 1 //對(duì)角＋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
}

危險(xiǎn)的遞歸解法

str1的一個(gè)子序列相應(yīng)于下標(biāo)序列{1, 2, …, m}的一個(gè)子序列，因此，str1共有${2^m}$個(gè)不同子序列（str2亦如此，如為${2^n}$），因此復(fù)雜度達(dá)到驚人的指數(shù)時(shí)間（${2^m * 2^n}$）。

//警告，字符串的長(zhǎng)度一大就會(huì)爆棧
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
  }
 }

參考鏈接

• http://blog.csdn.net/hrn1216/article/details/51534607
• https://segmentfault.com/a/1190000002641054
• https://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html
• http://www.cppblog.com/mysileng/archive/2013/05/14/200265.html

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論