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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.



  • 0
    reliably_not_huy  commented on Feb. 9, 2024, 1:47 p.m.

    Xâu thứ 2 của test mẫu 4 :)))


  • -3
    playerno1  commented on Dec. 3, 2023, 2:00 p.m.

    .


  • -2
    tonblan  commented on Nov. 23, 2023, 2:58 a.m.

    another reason to nerf chamber


  • -3
    brianthecrab  commented on Oct. 16, 2023, 12:39 p.m.

    Phạm đăng việt bách 2k8 THPT CHUYÊN KHTN NĂM 2024 SẼ THI IOI


  • -2
    Cuunon311  commented on Oct. 9, 2023, 3:30 p.m.

    bai nay hay


  • -11
    DoanHoangLong  commented on Aug. 6, 2023, 8:46 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -19
    vndkhoi  commented on June 17, 2023, 3:43 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -30
    how_to_get_her_love999  commented on May 3, 2023, 8:01 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -23
    FarisNya_2  commented on April 9, 2023, 3:54 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -60
    sickboy1368  commented on Oct. 7, 2021, 2:03 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.