2024年11月13日 星期三

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"

沒有留言:

張貼留言