/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。
注釈
文字列 x の部分列とは、x から 0 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。
制約
- s および t は英小文字からなる文字列である。
- 1 \leq |s|, |t| \leq 3000
入力
入力は以下の形式で標準入力から与えられる。
s t
出力
s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。
入力例 1
axyb abyxb
出力例 1
axb
答えは axb または ayb です。
どちらを出力しても正解となります。
入力例 2
aa xayaz
出力例 2
aa
入力例 3
a z
出力例 3
答えは (空文字列) です。
入力例 4
abracadabra avadakedavra
出力例 4
aaadara
Score : 100 points
Problem Statement
You are given strings s and t. Find one longest string that is a subsequence of both s and t.
Notes
A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.
Constraints
- s and t are strings consisting of lowercase English letters.
- 1 \leq |s|, |t| \leq 3000
Input
Input is given from Standard Input in the following format:
s t
Output
Print one longest string that is a subsequence of both s and t. If there are multiple such strings, any of them will be accepted.
Sample Input 1
axyb abyxb
Sample Output 1
axb
The answer is axb or ayb; either will be accepted.
Sample Input 2
aa xayaz
Sample Output 2
aa
Sample Input 3
a z
Sample Output 3
The answer is (an empty string).
Sample Input 4
abracadabra avadakedavra
Sample Output 4
aaadara