分享到plurk 分享到twitter 分享到facebook

版本 626fa16d9c9f9a834506e3d8801acfee17b0f8b7

acm/course/LCS

Define
    Find a sub-sequence of 2 given sequences in which the sub-sequence`s elements are appear in both original sequences. And the sub-sequence is as long as possible.
    ex: ‘aabbcc’, ‘abbccc’ => ‘abc’

What do we want to know?
    – The LCS of S1[1…i] and S2[1…j].
    – i.e. LCS[i][j]


How can we get that?
    – Find the previous number with longest LIS.
    – LCS[i][j]:
      0 , i=0 or j=0 LCS[i-1][j-1]+1 , S1[i]=S2[j] max(LCS[i-1][j],LCS[i][j-1]) , S1[i]≠S2[j]
    ex: ‘CBABCABCC’ , ‘ABCABCBA’ => ABCABC