Atcoder Educational DP Contest F - LCS

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bạn được cho hai xâu ~s~ và ~t~. Hãy tìm xâu con chung dài nhất của hai xâu đó.

Lưu ý: Xâu con của xâu ~x~ là xâu được tạo bằng cách xóa ~0~ hoặc một số kí tự thuộc xâu ~x~ và nối các kí tự còn lại mà không thay đổi vị trí của chúng.

Input

Dòng đầu tiên chứa xâu ~s~ ~(1 \le \left| s \right| \le 3000)~.

Dòng thứ hai chứa xâu ~t~ ~(1 \le \left| t \right| \le 3000)~.

Các kí tự của ~s~ và ~t~ đều là các chữ cái Tiếng Anh in thường.

Output

Xuất ra xâu con chung dài nhất của ~s~ và ~t~. Nếu có nhiều xâu thỏa mãn, in ra một xâu bất kì trong các xâu đó.

Sample 1

Input
axyb
abyxb
Output
axb

Kết quả là axbayb đều được chấp nhận.

Sample 2

Input
aa
xayaz
Output
aa

Sample 3

Input
a
z
Output

Kết quả có thể là xâu rỗng.

Sample 4

Input
abracadabra
avadakedavra
Output
aaadara

Comments

Please read the guidelines before commenting.