現在要求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