Educational DP Contest AtCoder F - LCS - Olympiads Online Judge

Educational DP Contest AtCoder F - LCS

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 1G

Problem type

You are given strings $s$ ~s~ and $t$ ~t~. Find one longest string that is a subsequence of both $s$ ~s~ and $t$ ~t~.

Notes

A subsequence of a string $x$ ~x~ is the string obtained by removing zero or more characters from $x$ ~x~ and concatenating the remaining characters without changing the order.

Constraints

$s$ ~s~ and $t$ ~t~ are strings consisting of lowercase English letters.
$1 \le |s|, |t| \le 3000$ ~1 \le |s|, |t| \le 3000~

Input Specification

The first line of input will contain a string $s$ ~s~.

The second line of input will contain a string $t$ ~t~.

Output Specification

You are to print out, on a single line, one longest string that is a subsequence of both $s$ ~s~ and $t$ ~t~. If there are multiple such strings, any of them will be accepted.