문제는 2 개의 문자열 X와 Y가 주어진 경우, 두 개의 문자열이 Z의 하위 시퀀스로 발생하도록 가장 짧은 시퀀스 Z의 길이를 찾아야한다는 것입니다. 이제 길이 = | X 인 직감을 얻습니다. | + | Y | - | LCS (X, Y) |. 그러나 어떻게 증명할 수 있습니까?
가장 짧은 공통 SuperSequence
예 : X = AGGTAB, Y = GXTXAYB, Z = AGXGTXAYB 및 | Z | = 9. LCS (X, Y) = GTAB
하자 문자열 1 일 2
는 S가 시퀀스로 두 X 및 Y로 구성되어있는 최단 슈퍼 시퀀스하자 문자열 . 그런 시퀀스를 만들어 봅시다.
주 :
분명히, X는 따라서 S.의 순서로 존재 초기 S는로 표시 될 수 '...'장소는 비어 있거나 할 수 할 수있는 수단 X와 Y로 구성된 최단 수퍼 시퀀스가되도록 Y의 문자를 배치하는 데 사용됩니다.
자, this | S | 최소가되어야합니다. 우리는 X와 Y로 구성된 최단 수퍼 시퀀스를 만들기 위해 Y의 최소 문자 만이 S에 주입해야합니다. 또한 Y는 하위 시퀀스로 나타나야하고 하위 문자열로 나타나지 않아야한다는 조건이 있음을 유의하십시오. 따라서 X에서 Y의 문자 시퀀스가 발견되면 Y 문자를 삽입 할 필요가 없습니다.
따라서 | S | 최소가되도록 Y를 삽입해야 시퀀스가 Y가됩니다. 이를 위해 우리는 Y에서 일어나는 가장 긴 X의 시퀀스를 발견한다. 즉 Y = LCS (X, Y)이다.
| S | = | X | + (| Y | - | LCS (X, Y) |) = | X | + | Y | - | LCS (X, Y) |
이제 여러 개의 LCS (X, Y)가 있습니다. any를 취하여 시퀀스를 구성하십시오.
먼저 보내 두 번째 링크에서 찾고, 그 크기 인 슈퍼 시퀀스를 만들 수 있습니다 | X를 | + | Y | - | LCS (X, Y) | : 두 개의 입력 시퀀스를 들어
는, SCS가 가장 긴 일반적인 서브 형성 될 수있다 (LCS)을 쉽게 ...
는 이제 모든되어 남아 그것이 실제로 가장 짧은 일반적인 supersequence임을 증명합니다. 반대로 가정하면, 길이가 | X |가되도록 가장 짧은 공통 수퍼 시퀀스가 있다고 가정합니다. + | Y | - | LCS (X, Y) | - 1 == | X | + | Y | - (| LCS (X, Y) | + 1). 그러나이 문자열에서 X는 서브 시퀀스로, Y는 서브 시퀀스로 나타납니다. 그것은 LCS (X, Y) |에서 교차한다는 것을 의미합니다. 문자열의 크기에 따라 판단하는 + 1 곳. LCS 크기가 | LCS (X, Y) | + 1, LCS의 정의에 대한 모순!
따라서 크기는 정확히 | X | + | Y | - | LCS (X, Y) |. q.e.
글자의 개수 만 신경 쓰면 모든 시퀀스 (X, Y, Z 및 LCS (X, Y))를 정렬 할 수 있습니다. 이는 정렬 순서 (최소 연속 문자와 LCS를 계산 한 후)가 문자의 수를 동일하게 유지하기 때문입니다.
정렬 된 시퀀스를 고려하는 경우 1 문자로 구성된 시퀀스 만 고려하면됩니다. 이는 각 시퀀스의 각 문자 수가 각 시퀀스의 다른 모든 문자 수와 독립적이기 때문입니다.
이제 단 하나의 문자로 구성된 시퀀스를 고려하면 X와 Y를 하위 시퀀스로 포함하는 최소 시퀀스는 X 또는 Y 중 하나이며 LCS (X, Y)는 다른 것. 그래서 (최소한의 포함 시퀀스에 대해 표기법 "MCS"를 적용) | MCS (X, Y) | + | LCS (X, Y) | = | X | + | Y |.
"LCS (X, Y) | +1 곳에서 교차한다는 의미입니다."어떻게 증명하나요? –
그냥 문자열의 크기를보고 – PartlyCloudy
나는 문자열의 크기를보고 어떻게 이해할 수 없다 나는 결론을 | LCS (X, Y) | +1 교차로. 이 점에 대해 좀 더 자세히 설명해주십시오. 내가 아는 나머지 증거들. –