#AT6. LCS
LCS
Original Problem Statement (English)
Source: AtCoder Educational DP Contest - Problem F
Problem Statement
You are given strings and . Find one longest string that is a subsequence of both and .
Notes
A subsequence of a string is the string obtained by removing zero or more characters from and concatenating the remaining characters without changing the order.
Constraints
- and are strings consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
t
Output
Print one longest string that is a subsequence of both and . 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