Longest Common Subsequence (LCS)

 計算兩個字串的 Longest Common Subsequence (LCS) 長度。讓我們逐步追踪程式執行的過程，並解釋每個步驟。

---

程式邏輯

字串

• x = 'abcdef'
• y = 'bcdk'

動態規劃矩陣

• 矩陣 c 的大小為 (lx+1) x (ly+1)，即 7 x 5。
• 初始值均為 0，例如：

c = [
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]
]

---

追踪計算過程

外層迴圈 i 遍歷 x 的字元

• 遍歷字串 x 的每個字元，從 1 到 lx（6）。

內層迴圈 j 遍歷 y 的字元

• 對應字串 y 的每個字元，從 1 到 ly（4）。

填充規則

1. 如果 x[i-1] == y[j-1]（字元相同）：
   • c[i][j] = c[i-1][j-1] + 1
2. 如果字元不同：
   • c[i][j] = max(c[i-1][j], c[i][j-1])

---

步驟詳解

1. 初始化：

   • 矩陣大小為 7x5，初始為全 0。

2. 計算過程：

   • i=1 (x[0]=‘a’):

     • j=1 (y[0]=‘b’): 不相等，c[1][1] = max(c[0][1], c[1][0]) = 0
     • j=2 (y[1]=‘c’): 不相等，c[1][2] = max(c[0][2], c[1][1]) = 0
     • j=3 (y[2]=‘d’): 不相等，c[1][3] = max(c[0][3], c[1][2]) = 0
     • j=4 (y[3]=‘k’): 不相等，c[1][4] = max(c[0][4], c[1][3]) = 0

   • i=2 (x[1]=‘b’):

     • j=1 (y[0]=‘b’): 相等，c[2][1] = c[1][0] + 1 = 1
     • j=2 (y[1]=‘c’): 不相等，c[2][2] = max(c[1][2], c[2][1]) = 1
     • j=3 (y[2]=‘d’): 不相等，c[2][3] = max(c[1][3], c[2][2]) = 1
     • j=4 (y[3]=‘k’): 不相等，c[2][4] = max(c[1][4], c[2][3]) = 1

   • i=3 (x[2]=‘c’):

     • j=1 (y[0]=‘b’): 不相等，c[3][1] = max(c[2][1], c[3][0]) = 1
     • j=2 (y[1]=‘c’): 相等，c[3][2] = c[2][1] + 1 = 2
     • j=3 (y[2]=‘d’): 不相等，c[3][3] = max(c[2][3], c[3][2]) = 2
     • j=4 (y[3]=‘k’): 不相等，c[3][4] = max(c[2][4], c[3][3]) = 2

   • i=4 (x[3]=‘d’):

     • j=1 (y[0]=‘b’): 不相等，c[4][1] = max(c[3][1], c[4][0]) = 1
     • j=2 (y[1]=‘c’): 不相等，c[4][2] = max(c[3][2], c[4][1]) = 2
     • j=3 (y[2]=‘d’): 相等，c[4][3] = c[3][2] + 1 = 3
     • j=4 (y[3]=‘k’): 不相等，c[4][4] = max(c[3][4], c[4][3]) = 3

   • i=5 (x[4]=‘e’):

     • j=1 (y[0]=‘b’): 不相等，c[5][1] = max(c[4][1], c[5][0]) = 1
     • j=2 (y[1]=‘c’): 不相等，c[5][2] = max(c[4][2], c[5][1]) = 2
     • j=3 (y[2]=‘d’): 不相等，c[5][3] = max(c[4][3], c[5][2]) = 3
     • j=4 (y[3]=‘k’): 不相等，c[5][4] = max(c[4][4], c[5][3]) = 3

   • i=6 (x[5]=‘f’):

     • j=1 (y[0]=‘b’): 不相等，c[6][1] = max(c[5][1], c[6][0]) = 1
     • j=2 (y[1]=‘c’): 不相等，c[6][2] = max(c[5][2], c[6][1]) = 2
     • j=3 (y[2]=‘d’): 不相等，c[6][3] = max(c[5][3], c[6][2]) = 3
     • j=4 (y[3]=‘k’): 不相等，c[6][4] = max(c[5][4], c[6][3]) = 3

---

最終矩陣

c = [
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1],
 [0, 1, 2, 2, 2],
 [0, 1, 2, 3, 3],
 [0, 1, 2, 3, 3],
 [0, 1, 2, 3, 3]
]

---

輸出結果

LCS 長度: 3

---

解釋

• c[lx][ly] = c[6][4] = 3 表示字串 x 和 y 的 Longest Common Subsequence 長度為 3。
• 最長公共子序列為 "bcd"。