公共子序列(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的公共子序列，其長度為3。但Z不是X和Y的最長公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均為X和Y的最長公共子序列，長度為4 ，而X和Y不存在長度大於等於5的公共子序列。對於序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。
我們專注於留意」子序列「的概念，它可以刪掉多個或零個，也可以全部幹掉。這時我們的第一個子序列為 空字串 （如果我們的序列不是字串，我們還可以 ）！這個真是千萬要注意到！許多人就是看不懂《演算法導論》的那張圖表，還有許多部落格的作者不懂裝懂。我們總是從左到右比較，當然了第一個字串，由於作為矩陣的高，就垂直放置了。
#然後我們X不動，繼續讓空字串出陣，Y讓「B」出陣，很顯然，它們的公共區域的長度為0. Y換成其他字符， D啊，C啊， 或者， 它們的連續組合DC、 DDC， 情況沒有變， 依然為0. 因此第一行都為0. 然後我們Y不動，Y只出空字任串，那麼與上面的分析一樣，都為0，第一列都是0.
如果X只從派出前面個字符A,B吧，亦即是“”，“A”, "B", "AB"這四種組合，前兩個已經解說過了。那我們先看B，${X_1} == ${Y_0}， 我們得到一個新的公共子字串了，應該要加1。為什麼呢？因為我們這個矩陣是一個狀態表，從左到右，從上到下描述狀態的遷移過程，而這些狀態是基於已有狀態 累加 出來的。 現在我們要確認的是，現在我們要填的這個格子的值與它周圍已經填好的格子的值是存在何種關係 。目前，資訊太少，就是一個孤點，直接填1。
如果比較的字元一樣呢，稍安毋躁，剛好X的C要與Y的C進行比較，即ABC的子序列集合{"",A,B,C,AB,BC, ABC}與BDC的子序列集合｛"",B,D,C,BD,DC,BDC｝比較，得到公共子字串有「」,B,D 。這時還是與先前的結論一樣，當字元相等時，它對應的格子值等於左邊與右邊與左上角的值，並且左邊，上邊，左上邊總是相等的。這些奧秘需要更嚴格的數學知識來論證。
假設有兩個數組，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)。這就推出了與反正假設矛盾的結果。
得證。
我們現在用下面的方程式來繼續填表了。
程式實作
//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
}
}
我相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！ 推薦閱讀：
datepicker怎麼使用
NavigatorIOS元件的使用詳解
#ejsExcel範本在Vue.js中的使用
以上是JS如何做出公共子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
#D