Problem : 353 - LSLCS

Problem Statistics

Solved Member: 10　　Submission: 84　　User Tried: 15

Statement:

給你兩個字串A, B

我們定義LCS(A,B)為A跟B的最長共同子序列。
子序列的定義是，一個序列刪除某幾項之後的新序列（可以是不連續的）。
例如，ADE是ABCDE的一個子序列。

現在給你兩個都只有小寫英文字母的字串，請問他們的最長共同子序列是哪一條。

感覺很簡單，但因為有很多條，所以要問的是字典序最小的是哪一條。

Lexicographically Smallest Longest Common Subsequence

哈哈，沒這麼簡單了吧 (A_______A)

Input:Output:

給你兩個字串，每個字串佔一行，共兩行，字串長度介於1~3000。

請輸出一行，包含字典序最小的LCS。

Sample Input:Sample Output:

qwoerijkjvzlkxncvlnlhihandsomebrotherqjwoirywoiethaoishdgksd
dfiwehriuhsejkashdgjkstaidajiayouasfjakwjegkjsngmzsndgmsbgj

werijkadstjiyoasgksd

Source:

2014 北市賽培訓

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	10
2	1000ms	262144kb	10
3	1000ms	262144kb	10
4	1000ms	262144kb	10
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7	1000ms	262144kb	10
8	1000ms	262144kb	10
9-1	1000ms	262144kb	10
9-2	1000ms	262144kb
10-1	1000ms	262144kb	10
10-2	1000ms	262144kb