最长公共序列算法 _最长公共序列算法

LCS-LENGTH (X, Y) 1. m ← length [X] 2. n ← length [Y] 3. for i ← 1 to m 4. do c [i, 0] ← 0 5. for j ← 0 to m 6. do c [0, j] ← 0 7. for i ← 1 to m 8. do for j ← 1 to n 9. do if xi= yj 10. then c [i, j] ← c [i-1, j-1] + 1 11. b [i, j] ← "↖" 12. else if c[i-1, j] ≥ c[i, j-1] 13. then c [i, j] ← c [i-1, j] 14. b [i, j] ← "↑" 15. else c [i, j] ← c [i, j-1] 16. b [i, j] ← "← " 17. return c and b.

最长公共序列的示例 【最长公共序列算法】示例：给定两个序列X [1 … m]和Y [1 … .. n]。找到两者的最长共同子序列。

文章图片

here X = (A, B, C, B, D, A, B) and Y = (B, D, C, A, B, A)m = length [X] and n = length [Y]m = 7 and n = 6Here x1= x [1] = Ay1= y [1] = Bx2= By2= D x3= Cy3= Cx4= By4= Ax5= Dy5= Bx6= Ay6= Ax7= BNow fill the values of c [i, j] in m x n tableInitially, for i=1 to 7 c [i, 0] = 0For j = 0 to 6 c [0, j] = 0

那是：

文章图片

Now for i=1 and j = 1 x1 and y1 we get x1 ≠ y1 i.e. A ≠ BAndc [i-1, j] = c [0, 1] = 0 c [i, j-1] = c [1, 0 ] = 0That is, c [i-1, j]= c [i, j-1] so c [1, 1] = 0 and b [1, 1] = ' ↑'Now for i=1 and j = 2x1 and y2 we get x1 ≠ y2 i.e. A ≠ D c [i-1, j] = c [0, 2] = 0 c [i, j-1] = c [1, 1 ] = 0That is, c [i-1, j]= c [i, j-1] and c [1, 2] = 0 b [1, 2] = '↑'Now for i=1 and j = 3 x1 and y3 we get x1 ≠ y3 i.e. A ≠ C c [i-1, j] = c [0, 3] = 0 c [i, j-1] = c [1, 2 ] = 0so c [1, 3] = 0b [1, 3] = ' ↑ 'Now for i=1 and j = 4 x1 and y4 we get. x1=y4 i.e A = A c [1, 4] = c [1-1, 4-1] + 1= c [0, 3] + 1= 0 + 1 = 1 c [1, 4] = 1 b [1, 4] = '↖'Now for i=1 and j = 5x1 and y5we get x1 ≠ y5c [i-1, j] = c [0, 5] = 0 c [i, j-1] = c [1, 4 ] = 1Thus c [i, j-1] > c [i-1, j] i.e. c [1, 5] = c [i, j-1] = 1. So b [1, 5] = '←'Now for i=1 and j = 6x1 and y6we get x1=y6c [1, 6] = c [1-1, 6-1] + 1= c [0, 5] + 1 = 0 + 1 = 1c [1, 6] = 1b [1, 6] = '↖'

文章图片

Now for i=2 and j = 1 We get x2 and y1 B = B i.e.x2= y1c [2, 1] = c [2-1, 1-1] + 1= c [1, 0] + 1= 0 + 1 = 1c [2, 1] = 1 and b [2, 1] = ' ↖ 'Similarly, we fill the all values of c [i, j] and we get

文章图片
步骤4：构建LCS：初始调用为PRINT-LCS（b, X, X.length, Y.length）

PRINT-LCS (b, x, i, j) 1. if i=0 or j=0 2. then return 3. if b [i, j] = ' ↖ ' 4. then PRINT-LCS (b, x, i-1, j-1) 5. print x_i 6. else if b [i, j] = '↑' 7. then PRINT-LCS (b, X, i-1, j) 8. else PRINT-LCS (b, X, i, j-1)

示例：确定（1, 0, 0, 1, 0, 1, 0, 1）和（0, 1, 0, 1, 1, 0, 1, 1, 0）的LCS。
解：让X =（1, 0, 0, 1, 0, 1, 0, 1）和Y =（0, 1, 0, 1, 1, 0, 1, 1, 0）。