Week 6 : LCS (Longest Common Sub-sequence)

##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’