D | 0 |
| A | 0 |
B |
0 |
|
そして、2 つの文字列間で比較される文字が異なる場合、塗りつぶされるグリッドは左辺または上辺に関連しており、大きい方の辺が使用されることは確実です。
比較される文字が同じ場合でも、心配する必要はありません。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 などの面倒な中間量の使用を避けるために、プログラムが実行されるたびに 1 つの文字列のみが返され、それ以外の場合は 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 値があることに注意してください。これは、実際には 3 つの状況を統合します。したがって、3本の弦をフォークすることができます。このメソッドは、自動削除のために 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、…、aしたがって、str1 には合計 ${2^m}$ 個の異なる部分列があり (${2^n}$ などの str2 にも同じことが当てはまります)、そのため複雑度は驚くべき指数関数的時間 ($) に達します。 { 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
}
}
関連する推奨事項:
Python 言語で最大連続部分列和を説明する
最大連続部分列和問題
最大部分列和のための PHP アルゴリズムの実装_PHP チュートリアル
|
