LCS 알고리즘의 서브 시퀀스 란 무엇입니까?

Question

저는 지난 주 LCS 문제에 대한 연구를 해왔으며 질문이 있습니다.

길이가 아닌 서브 시퀀스 자체를 찾는 데 관심이있을 때마다 보조 (string1.length X string2.length) 행렬을 작성하여 화살표가 왼쪽으로 합쳐져서 서브 시퀀스가 ​​무엇인지 알아냅니다 화살표 또는 대각선 화살표, 우리가 어디서 왔는지에 따라 나중에 단계를 되돌아보고 하위 시퀀스 자체를 찾을 수 있습니다.

내 질문은 이것이다 :

(마지막 페이지에 http://www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf 여기 예 참조) 생각이 두 문자열을 실행하기 위해 다음과 같은 출력 매트릭스 :

- 0 0 0 0 0 0 0 0 0 0 0 
- 0 0 0 0 0 0 0 1 1 1 1 
- 0 0 0 0 0 0 0 1 2 2 2 
- 0 0 0 0 0 0 0 1 2 3 3 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 1 1 1 2 3 4 
- 0 0 0 1 1 2 2 2 2 3 4 

: LCS를 통해 "abfcytyruc"와 "vxczcxabfc을"

더 복잡한 공간을 필요로하지 않고 행렬의 마지막 열만을 기반으로 일반적인 하위 시퀀스를 찾을 수 있다는 것은 사실입니까?

Answer 1

위의 간단한 동적 프로그래밍 방법을 사용할 때 마지막 열에는 LCS의 길이를 결정할 수 있지만 실제 순서는 결정할 수 없습니다. 여기

실패 예 :

a a a a a c b b 
c 0 0 0 0 0 1 1 1 
b 0 0 0 0 0 1 2 2 
b 0 0 0 0 0 1 2 3 
a 1 1 1 1 1 1 2 3 
a 1 2 2 2 2 2 2 3 
a 1 2 3 3 3 3 3 3 
a 1 2 3 4 4 4 4 4 

은 Hirschberg 알고리즘에서보세요. 이것은 Needleman-Wunsch 알고리즘의 분할 및 정복이며 선형 공간에서 작동합니다.

추가 읽기 : http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/05/Hirschberg75.pdf