版本 626fa16d9c9f9a834506e3d8801acfee17b0f8b7

acm/course/LCS

Changes from 626fa16d9c9f9a834506e3d8801acfee17b0f8b7 to current

Define<br/>
<ul> 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. </ul>
Week 6 : LCS (Longest Common Sub-sequence)
========
##Define
<ul> 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.`** </ul>
<ul> ex: 'aabbcc', 'abbccc' => 'abc'</ul>
<br/>
What do we want to know?

##What do we want to know?
<ul> – The LCS of S1[1...i] and S2[1...j]. </ul>
<ul> – i.e. LCS[i][j] </ul><br/>

How can we get that?
##How can we get that?
<ul>– Find the previous number with longest LIS. </ul>
<ul>– LCS[i][j]:
 <ul>
 <ul>```c++
     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]
```
 </ul>
</ul>
<ul>
ex: 'CBABCABCC' , 'ABCABCBA' => ABCABC<br/>
ex: 'CBABCABCC' , 'ABCABCBA' => 'ABCABC'<br/>
 <img src="http://wiki.csie.ncku.edu.tw/acm/LCS-1.png" height="200" width="200"/>
 <img src="http://wiki.csie.ncku.edu.tw/acm/LCS-2.png" height="200" width="200"/>
 <img src="http://wiki.csie.ncku.edu.tw/acm/LCS-3.png" height="200" width="200"/>
 <img src="http://wiki.csie.ncku.edu.tw/acm/LCS-4.png" height="200" width="200"/>
</ul>