Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 contact Rimuru or Ninjaclasher on slack.

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
    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?


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

      You shouldn't store the string for each dp value


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

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