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