計算兩個字串的 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)。
填充規則
- 如果
x[i-1] == y[j-1]
(字元相同):c[i][j] = c[i-1][j-1] + 1
- 如果字元不同:
c[i][j] = max(c[i-1][j], c[i][j-1])
步驟詳解
初始化:
- 矩陣大小為
7x5
,初始為全0
。
- 矩陣大小為
計算過程:
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"
。
沒有留言:
張貼留言