최장 공통 부분 수열
두 개의 수열에 대한 해 > 예시

C = (AGCAT)와 R = (GAC)의 최장 공통 부분순열을 찾을것이다. LCS 함수는 "0번째"원소를 이용하기 때문에, 이 수열에서 비어있는 0번째 접두사를 정의하는 것이 편리하다. C0 = Ø, 그리고 R0 = Ø이다. 모든 접두사들은 C를 첫 번째 행에 위치하고, R을 첫 열에 위치시킨 표에 자리잡는다.
|  | 0 | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
0: Ø
| G | Ø |  |  |  |  |  |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |

이 표는 연산의 각 단계에서 LCS 수열을 저장하는데 이용된다. 두 번째 행과 두 번째 열은 Ø로 채워지는데, 빈 수열이 비어있지 않은 수열과 비교될 때 가장 긴 공통 부분 수열이 항상 빈 수열이 되기 때문이다.
LCS(R1, C1)는 각 수열의 첫 원소를 비교함으로써 결정된다. G와 A는 일치하지 않기 때문에, 이것의 LCS는 두 번째 속성에 의해 두 수열 LCS(R1, C0) 와 LCS(R0, C1)중 긴 것을 갖게 된다.
표에서 보면, 이 둘 모두 비어있기 때문에 LCS(R1, C1) 도 마찬가지로 아래쪽 표에서 볼 수 있듯이 비어있게 된다. 화살표는 수열이 위쪽의 두 셀 LCS(R0, C1) 과 그 왼쪽 셀인 LCS(R1, C0)에서 온다는 것을 가리킨다.
LCS(R1, C2)는 G와 G를 비교함으로써 결정된다. 그들은 동일하므로, 왼쪽 위의 (Ø)의 수열LCS(R0, C1)뒤에 붙어서 (ØG)가 되므로 결과적으로 (G)가 된다.
LCS(R1, C3)에서, G와 C는 일치하지 않는다. 그 위의 수열은 비어있고, 그 왼쪽의 것은 G라는 하나의 원소를 포함한다. 이들중 가장 긴 것을 선택하면 LCS(R1, C3)는 (G)가 된다. 화살표는 왼쪽을 가리키는데, 그것이 둘중 가장 긴 것이기 때문이다.
LCS(R1, C4)는 같은 방법으로 (G)이다.
LCS(R1, C5)또한 같은 방법으로 (G)이다.
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |

LCS(R2, C1)에서, A는 A와 비교된다. 두 원소가 동일하므로, A는 Ø에 첨가되어 (A)가 된다.
LCS(R2, C2)에서, A와 G는 같지 않다. 따라서 두 수열LCS(R1, C2)와 LCS(R2, C1)중 가장 긴 것, 즉 (G)와 (A)중 가장 긴 것이 사용된다. 이 예시에서 그들은 하나의 원소만들 포함하므로, LCS는 두 부분 수열 (A)와 (G)로 주어진다.
LCS(R2, C3)에서, A는 C와 동일하지 않다. LCS(R2, C2)는 수열 (A) 와 (G)를 포함한다. LCS(R1, C3)는 (G)로, LCS(R2, C2)에 이미 포함되어있다. 결과적으로 LCS(R2, C3) 또한 두 수열 (A) 와 (G)를 포함한다.
LCS(R2, C4)의 경우, A는 A와 같으므로, 왼쪽 위 셀에 붙어, (GA)가 된다.
LCS(R2, C5)의 경우에서, A는 T와 같지 않다. 두 수열 (GA) 와 (G)를 비교했을 때, 가장 긴것은 (GA)이므로LCS(R2, C5)는 (GA)이다.
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(GA) |
| C | Ø |  |  |  |  |  |

LCS(R3, C1)에서, C 와 A는 같지 않으므로, LCS(R3, C1)는 가장 긴 수열 (A)를 갖는다.
LCS(R3, C2)에서, C 와 G는 같지 않다. LCS(R3, C1) 와 LCS(R2, C2) 모두 단 하나의 원소를 가지므로 LCS(R3, C2)는 두 원소 (A) 와 (G)를 가지게 된다.
LCS(R3, C3)에서, C 와 C는 동일하므로, C는 두 부분수열 (A)와 (C)를 포함하는 LCS(R2, C2)에 붙어 (AC) 와 (GC)가 된다.
LCS(R3, C4)에서, C와 A는 같지 않다. (AC)와 (GC)를 포함하는 LCS(R3, C3)와 (GA)를 포함하는 LCS(R2, C4)를 조합하면 총 세 개의 수열 (AC), (GC), 그리고 (GA)를 준다.
마지막으로, LCS(R3, C5)에 대해서, C와 T는 일치하지 않는다. 결과적으로 LCS(R3, C5) 또한 세 수열 (AC), (GC), 그리고 (GA)를 갖는다.
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }}Ø |  {\overset {\nwarrow }{\ }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |  {\overset {\ }{\leftarrow }}(G) |
| A | Ø |  {\overset {\nwarrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(GA) |  {\overset {\ }{\leftarrow }}(GA) |
| C | Ø |  {\overset {\ \uparrow }{\ }}(A) |  {\overset {\ \ \uparrow }{\leftarrow }}(A) & (G) |  {\overset {\nwarrow }{\ }}(AC) & (GC) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |  {\overset {\ \ \uparrow }{\leftarrow }}(AC) & (GC) & (GA) |

최종 결과는 마지막 셀이 (AGCAT)와 (GAC)의 모든 최장 공통 부분 수열을 포함한다는 것을 보여준다. 그 셀은 (AC), (GC), 그리고 (GA)를 가진다. 이 표는 또한 모든 가능한 접두사의 쌍에 대한 최장 공통 부분 수열을 보여준다. 예를 들어, (AGC)와 (GA)에 대해서, 최장 공통 부분 수열은 (A)와 (G)이다.