重建最長共同子序列

題目敘述

小墨助教要比對兩位同學交上來的字串 s 與 t。若某個字串能同時從 s 和 t 刪掉若干字元（不改變剩下字元的順序）後得到，它就是兩者的共同子序列。請輸出一個最長的共同子序列（LCS）。若沒有任何共同字元，輸出一個空行。

同長度的答案可能不只一個，為了讓輸出唯一，請依下列方式取得：

定義 L[i][j] 為 s 前 i 個字元與 t 前 j 個字元的 LCS 長度。從 (i,j)=(|s|,|t|) 出發，重複下列步驟直到 i=0 或 j=0：若 s_i=t_j，就取這個字元並移到 (i−1,j−1)；否則，若 L[i−1][j]≥ L[i][j−1] 就移到 (i−1,j)，不然移到 (i,j−1)。把取到的字元反過來排列即為答案。

輸入格式

共兩行。第 1 行是字串 s，第 2 行是字串 t。

輸出格式

輸出一行，為依上述方式得到的最長共同子序列。

限制

• 1 ≤ |s|,|t| ≤ 3000
• 字串只含小寫英文字母

範例

範例 1

輸入

axyb
abyxb

輸出

ayb

說明

最長長度是 3。axb 與 ayb 都是共同子序列，依上述回溯規則會得到 ayb。

範例 2

輸入

aa
xayz

輸出

a

說明

兩個 a 中只有一個能被取用，所以答案是單一個 a。

範例 3

輸入

axyb
abyxb

輸出

axb

說明

先填好 L 表，再依規則從右下角往回走。