Educational DP Contest AtCoder F - LCS

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type

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 \le |s|, |t| \le 3000

Input Specification

The first line of input will contain a string s.

The second line of input will contain a string t.

Output Specification

You are to print out, on a single line, 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 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


  • 0
    Xiang_li  commented on Aug. 10, 2021, 5:41 p.m.

    Case 105 is a big bully


  • 0
    animalright10  commented on May 8, 2021, 12:39 p.m.

    any advice of the last test case (105)? I got TLE on that one.


  • 1
    corgi  commented on April 6, 2020, 2:13 p.m.

    Any advice on how to not exceed memory? Do I have to do bottom-up?


    • 2
      Aaeria  commented on April 6, 2020, 4:35 p.m.

      You shouldn't store the string for each dp value


      • 4
        corgi  commented on April 6, 2020, 9:19 p.m.

        Thanks I got it. This should definitely be 10 points ¯\_(ツ)_/¯