Bài toán chuỗi con chung dài nhất
Thuật toán cho hai chuỗi > Làm việc với ví dụ

Để lấy ví dụ, ta sẽ tìm chuỗi con dài nhất chung cho hai xâu R = (GAC) và C = (AGCAT). Vì hàm LCS xét từ vị trí 0, nên để thuận tiện, ta sẽ xác định các tiền tố 0 là trống cho các chuỗi này: R0 = Ø; và C0 = Ø. Tất cả các tiền tố được đặt trong một bảng với C ở hàng đầu tiên và R ở cột đầu tiên:
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø
| G | Ø |  |  |  |  |  |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |

Bảng này được sử dụng để lưu trữ trình tự tính LCS cho mỗi bước tính toán. Cột thứ hai và hàng thứ hai đã được điền bằng Ø, bởi vì khi một chuỗi trống được so sánh với một chuỗi không trống, chuỗi con chung dài nhất luôn là chuỗi trống.
LCS (R1, C1) được xác định bằng cách so sánh các phần tử đầu tiên trong mỗi chuỗi. G và A không giống nhau, vì vậy LCS này nhận (sử dụng tính chất thứ hai trên) chuỗi dài nhất trong hai chuỗi, LCS(R1, C0) và LCS (R0, C1). Theo bảng, cả hai đều trống, vì vậy LCS (R1, C1) cũng trống. Các mũi tên biểu thị chuỗi nhập vào: chuỗi đến từ ô ở trên, LCS (R0, C1) và chuỗi đến từ ô ở bên trái, LCS(R1, C0).
LCS (R1, C2) được xác định bằng cách so sánh G và G. Chúng khớp với nhau, nên G được nối vào chuỗi phía trên bên trái, LCS(R0, C1), là (Ø), cho (ØG), ta được (G).
Đối với LCS (R1, C3), G và C không khớp. Chuỗi trên trống; Chuỗi bên trái chứa một phần tử, (G). Chọn phần tử có độ dài dài nhất trong hai chuỗi này, ta được LCS (R1, C3) là (G). Mũi tên chỉ sang trái, vì đó là chuỗi dài nhất trong hai chuỗi.
Tương tự như vậy, LCS(R1, C4) và LCS(R1, C5) là (G).
|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø
| G | Ø |  {\overset {\ \ \uparrow }{\leftarrow }} Ø |  {\overset {\nwarrow }{\ }} (G) |  {\overset {\ }{\leftarrow }} (G) |  {\overset {\ }{\leftarrow }} (G) |  {\overset {\ }{\leftarrow }} (G) |
| A | Ø |  |  |  |  |  |
| C | Ø |  |  |  |  |  |

Tương tự như vậy, ta hoàn thành hàng R2
|  | Ø | 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 | Ø |  |  |  |  |  |

Bảng hoàn thiện cuối cùng là
|  | Ø | 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) |

|  | Ø | A | G | C | A | T |
| --- | --- | --- | --- | --- | --- | --- |
Ø: 0
| G | 0 |  {\overset {\ \ \uparrow }{\leftarrow }} 0 |  {\overset {\nwarrow }{\ }} 1 |  {\overset {\ }{\leftarrow }} 1 |  {\overset {\ }{\leftarrow }} 1 |  {\overset {\ }{\leftarrow }} 1 |
| A | 0 |  {\overset {\nwarrow }{\ }} 1 |  {\overset {\ \ \uparrow }{\leftarrow }} 1 |  {\overset {\ \ \uparrow }{\leftarrow }} 1 |  {\overset {\nwarrow }{\ }} 2 |  {\overset {\ }{\leftarrow }} 2 |
| C | 0 |  {\overset {\ \uparrow }{\ }} 1 |  {\overset {\ \ \uparrow }{\leftarrow }} 1 |  {\overset {\nwarrow }{\ }} 2 |  {\overset {\ \ \uparrow }{\leftarrow }} 2 |  {\overset {\ \ \uparrow }{\leftarrow }} 2 |