現在要求X,Y的LCS X的長度為m, Y的長度為n 假設X,Y的一個LCS如下: 是1234567,長度為7 X: ..1..2..3..4....5...6....7. Y: .1....2...3....4...5..6.7.. 現在把X分為兩份: X[1]~X[m/2]為X1, X[m/2+1]~X[m]為X2 X: (..1..2..3..4.)(...5...6....7.) X1:..1..2..3..4. X2:...5...6....7. 現在選一個數t 把Y也分成兩段: Y[1]~Y[t]為Y1, Y[t+1]~Y[n]為Y2 如果我們選擇適當的t 可以分成如下的情況 Y1: .1....2...3....4 Y2: ...5..6.7.. 再看X和Y的情況 (..1..2..3..4.)(...5...6....7.) (.1....2...3....4)(...5..6.7..) 1234是X1和Y1的一個LCS, (不可能有更長的) 同樣的 567是X2和Y2的一個LCS 由此可知至少存在一個t 可以讓X1,Y1的LCS加上X2,Y2的LCS等於X,Y的LCS 再來只要分別去求X1,Y1和X2,Y2的LCS就行了 (如果t選得不好可能會比較小) 接下來就是技術上的問題: 如何求出t? 先求X1和Y的LCS,(只需要長度,所以可以像課本16.3-4所說的 b和c陣列都只要一維就可以,也就是最後一列) 求出以後,看看c所代表的意義, c1[n]代表X1和Y[1]~Y[n]的LCS長度 而 c1[i]代表X1和Y[1]~Y[i]的LCS長度 再來是X2和Y的LCS,這需要一點技巧,把X2和Y都反轉過來 再求LCS 如此 c2[i]代表X2和Y[n]~Y[n-i+1] 的LCS長度 有了這兩個陣列之後,就只要令t=0,1,2...n 看 c1[t]+c2[t] 裡面最大的就是了 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.70.150.14