JavaScript에서 가장 긴 공통 부분 수열에 대한 자세한 논의

가장 긴 공통 부분 수열은 주어진 두 수열 X와 Y에서 가능한 한 많은 문자를 취하여 원래 수열에 배열된 순서대로 배열하여 얻습니다. LCS 문제에 대한 알고리즘은 다양한 용도로 사용됩니다. 예를 들어, 다양한 버전의 소프트웨어를 관리할 때 LCS 알고리즘은 소프트웨어 테스트에서 이전 버전과 새 버전 간의 유사점과 차이점을 찾는 데 사용됩니다. 기록된 서열과 재생된 서열을 비교하는 데 사용됩니다. 유전 공학 분야에서는 LCS 알고리즘이 사용됩니다. 이 알고리즘은 표절 방지 시스템에서 환자의 DNA 가닥과 본드의 DNA 가닥 사이의 유사점과 차이점을 확인합니다. 논문의 표절률을 확인하는데 사용됩니다. LCS 알고리즘은 프로그램 코드 유사성 측정, 인간의 실행 시퀀스 검색, 비디오 세그먼트 매칭 등에 사용될 수 있으므로 LCS 알고리즘에 대한 연구는 응용 가치가 높습니다.

기본 개념

1. 하위 시퀀스: 특정 시퀀스의 하위 시퀀스는 주어진 시퀀스에서 0개 이상의 요소를 제거한 결과입니다(요소 간의 상대적 순서를 변경하지 않고). 예를 들어, 시퀀스 의 하위 시퀀스는 , , 잠깐만요.

2. 공통 부분 수열: 수열 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]의 공통 부분 수열에는 빈 수열 []만 있습니다.

3. 가장 긴 공통 부분 수열: X와 Y 수열이 주어지면 모든 공통 부분 수열 중에서 길이가 가장 긴 하나 또는 여러 개를 선택하세요.

4. 하위 문자열: 앞이나 끝에서 0개 또는 여러 개의 문자를 동시에 삭제하여 형성된 새로운 계열입니다. 차이점은 하위 시퀀스의 문자가 중간에서 잘려질 수 있다는 것입니다. cnblogs 문자열에는 몇 개의 하위 시퀀스가 ​​있습니까? 분명히 cb, cgs 등과 같은 27개의 하위 시퀀스가 ​​있습니다. 하위 문자열.

Problem Analysis

우리는 여전히 행렬에서 분석을 시작하고 상태 전이 방정식을 직접 도출합니다.

먼저 문제를 프론트 엔드에 충분히 친숙한 개념으로 변환합니다. 순차적으로 호출하는 대신 배열이나 문자열로 생각하면 됩니다. 일을 단순하게 유지하기 위해 두 문자열이 비교되고 있다고 가정해 보겠습니다.

여러 개, 0개 또는 모두를 삭제할 수 있는 "서브 시퀀스" 개념에 중점을 둡니다. 현재 첫 번째 하위 시퀀스는

빈 문자열

입니다(시퀀스가 문자열이 아닌 경우에도 가능합니다)! 정말 주목하셔야 할 부분이에요! "알고리즘 입문"의 차트를 이해하지 못하는 분들이 많고, 이해한 척 하지 않는 블로거들도 많습니다. 우리는 항상 왼쪽에서 오른쪽으로 비교하며, 물론 첫 번째 문자열은 행렬의 높이이므로 수직으로 배치됩니다.

CAB0

			""						A	B			D
												false order X = "ABCDAB", Y = "BDCABA", 각각 가장 짧은 시퀀스를 추출합니다. 즉, 빈 문자열과 빈 문자열을 비교합니다. LCS 방정식의 해는 숫자이기 때문에 이 표는 숫자로만 채워질 수 있습니다. 두 개의 빈 문자열의 공통 영역의 길이는 0.
""

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그런 다음 X를 이동하지 않고 계속해서 빈 문자열이 배열에서 나오도록 하고 Y에서는 "B"가 배열에서 나오도록 합니다. 분명히 공통 영역의 길이는 0입니다. Y는 다른 문자로 대체됩니다. , D, C 또는 연속성 DC와 DDC를 결합하면 상황은 변경되지 않았으며 여전히 0입니다. 따라서 첫 번째 행은 모두 0입니다. 그런 다음 Y를 이동하지 않고 Y는 빈 문자열만 생성합니다. 위 분석과 동일하며 둘 다 0이고 첫 번째 열은 모두 0입니다. 는 0.

0 00000LCS 문제는 배낭 문제와 조금 다릅니다. 배낭 문제는 -1 행으로 설정될 수도 있으며, 가장 긴 공통 부분 수열은 빈 부분 수열이 있기 때문에 처음부터 왼쪽과 위쪽이 고정되어 있습니다. 그러면 문제를 더 확대해 보겠습니다. 이번에는 양쪽이 모두 동일한 경우에만 빈 문자열이 아닌 공통 부분 수열이 있을 수 있으며 길이도 1로 이해될 수 있습니다. A는 "X"이고 Y는 "BDCA"BA

								""	0	0	0	0
							A	0	B	0	C	0	D
	A
	B
x	""
D	C

B

A

0 0001B1 계속해서 오른쪽 빈칸을 채워가는데, 빈칸은 어떻게 채우나요? 분명히 LCS는 X의 길이보다 클 수 없습니다. 어떻게 A 문자열에서 시작하는 Y의 하위 시퀀스가 ​​B의 A 시퀀스와 비교하여 1과 같을 수 있습니까? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 000B0C 그것이 ""라면 "A", "B", "AB"의 네 가지 조합 중 처음 두 개는 이미 설명되었습니다. 그런 다음 먼저 B(${X_1} == ${Y_0})를 살펴보고 새로운 공개 하위 문자열을 얻으며 1을 추가해야 합니다. 왜? 우리 매트릭스는 상태 테이블이기 때문에 왼쪽에서 오른쪽, 위에서 아래로 상태 마이그레이션 프로세스를 설명하고 이러한 상태는 기존 상태를 기반으로 누적됩니다 . 이제 확인해야 할 것은 우리가 채우려는 그리드의 값과 이미 채워져 있는 그 주변의 그리드 값 사이의 관계입니다. 현재는 정보가 너무 적어서 고립된 지점일 뿐입니다. 1개만 채워주세요.

								""	0	0	0	0
							A	0	0	0
												ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 1

"0000 0A0B0

0

0

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
1

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그런 다음 Y에게 도우미로 추가 D를 부여합니다. {"",A,B,AB} 대 {"",B,D,BD} 분명히 계속해서 1을 입력합니다. 의 두 번째 B까지 입력합니다. 네, 둘 다 1입니다. BDCAB의 경우 또 다른 공통 하위 시퀀스인 AB가 있기 때문입니다.

"00 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 1CD A0 B0Y는 모든 문자를 보냅니다. 이 경우 Y의 B 하위 시퀀스 집합은 더 커집니다. 비록 크지 않더라도 원본보다 작을 수는 없습니다. 분명히 새로 추가된 C는 전투력이 될 수 없고 둘 사이의 공통 문자가 아니므로 그 값은 AB의 하위 시퀀스 집합과 동일해야 합니다. "0000 000C

								0	0	0	0	0
						ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ				0		0
					이 단계에서는 계산을 통해 아이디어를 요약하고 새로운 규칙을 추가할 수 있습니다. 개선을 위한 조건을 제한합니다.
												ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 1
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

0

1# 0

그리고 두 문자열 사이에서 비교할 문자가 다른 경우 채워질 그리드는 왼쪽 또는 위쪽에 관련되고 더 큰 쪽이 사용된다는 것을 확신할 수 있습니다.

비교된 문자가 동일한 경우 걱정하지 마세요. 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 <p></p><p>LCS는 위치를 이동하는 것만으로 더욱 단순화할 수 있어 새 배열을 생성할 필요가 없습니다.</p><pre class="brush:php;toolbar:false">//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 <p></p><h2 id="LCS를-인쇄하세요">LCS를 인쇄하세요</h2><p>인쇄 기능을 제공하겠습니다. 먼저 인쇄하는 방법을 살펴보세요. 오른쪽 하단에서 시작하여 맨 위 줄에서 끝납니다. 따라서 대상 문자열은 역순으로 구성됩니다. stringBuffer와 같은 번거로운 중간 수량의 사용을 피하기 위해 프로그램이 실행될 때마다 하나의 문자열만 반환하고 그렇지 않으면 printLCS(x,y,...)를 사용하여 빈 문자열을 반환합니다. str[ i] 필요한 문자열을 얻기 위해 추가됩니다. </p><p>우리가 얻은 문자열이 실제 LCS 문자열인지 확인하는 또 다른 방법을 작성해 보겠습니다. 이미 일하고 있는 사람으로서, 나는 학교에서 학생처럼 코드를 작성하고 다른 사람들이 밟을 수 있도록 단위 테스트를 하지 않고는 온라인에 올릴 수 없습니다. </p><pre class="brush:php;toolbar:false">//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

Print all 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 0;1-0=>1; 1-1=>0 ...
    } 
    return row ? row[n]: 0
}

위험한 재귀 솔루션

str1의 하위 시퀀스는 아래 첨자 시퀀스에 해당합니다. 2, ... , m}의 하위 시퀀스입니다. 따라서 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 언어로 최대 연속 하위 시퀀스 합 설명

최대 연속 하위 시퀀스 합 문제

최대 하위 시퀀스 sum_PHP 튜토리얼을 위한 PHP 알고리즘 구현

위 내용은 JavaScript에서 가장 긴 공통 부분 수열에 대한 자세한 논의의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!