These problems are from the AtCoder DP contest, and were transferred onto DMOJ. All problem statements were made by several AtCoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please open a ticket by clicking the "Report an issue" button at the bottom of the page.
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 Specification
The first line of input will contain a string .
The second line of input will contain a string .
Output Specification
You are to print out, on a single line, 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 one 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
Comments
Case 105 is a big bully
any advice of the last test case (105)? I got TLE on that one.
Any advice on how to not exceed memory? Do I have to do bottom-up?
You shouldn't store the string for each dp value
Thanks I got it. This should definitely be 10 points ¯\_(ツ)_/¯