Atcoder Educational DP Contest F - LCS

Xem dạng PDF
Gửi bài giải
Điểm: 0,30 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Người đăng:
NoobCpp
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
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à axb và ayb đề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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 3
    lightloveyou2009  đã bình luận lúc 9, Tháng 12, 2025, 10:19 ← sửa 11

    Spoil

    https://ideone.com/OZ2L4I xin 1 upvote


  • 1
    vuonghoaitamdz9  đã bình luận lúc 9, Tháng 12, 2025, 10:16 ← sửa 6

    LCS


  • -11
    vdtue  đã bình luận lúc 6, Tháng 10, 2025, 11:59 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 2
    happynewy920  đã bình luận lúc 14, Tháng 3, 2025, 8:29

    bai hay qua


  • -8
    Backtin34  đã bình luận lúc 18, Tháng 12, 2024, 1:28 ← sửa 6

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    xthavan  đã bình luận lúc 30, Tháng 10, 2024, 13:53

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 16
    van353735  đã bình luận lúc 2, Tháng 9, 2024, 11:59

    xin upvote


  • -3
    sitingfake  đã bình luận lúc 24, Tháng 8, 2024, 13:09

    sao tịnh tiến s=" "+s dùng truy vết bằng đệ quy lại sai bruhbruh


    • 7
      Groot  đã bình luận lúc 2, Tháng 9, 2024, 13:31

      sitingfake mình có đọc code của bạn và thấy điều kiện này sai:

      if (dp[i][j] == dp[i - 1][j - 1] + 1)

      {

      trace(i - 1, j - 1);

      cout << s[i];

      }

      sửa lại phải là:

      if (s[i] == t[j])

      {

      trace(i - 1, j - 1);

      cout << s[i];

      }


  • -34
    vdtue  đã bình luận lúc 20, Tháng 8, 2024, 14:27

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -31
    phmducctintdn  đã bình luận lúc 14, Tháng 8, 2024, 9:19

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 5
    reliably_not_huy  đã bình luận lúc 9, Tháng 2, 2024, 13:47

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


  • -13
    playerno1  đã bình luận lúc 3, Tháng 12, 2023, 14:00

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -10
    tonblan  đã bình luận lúc 23, Tháng 11, 2023, 2:58

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -25
    brianthecrab  đã bình luận lúc 16, Tháng 10, 2023, 12:39 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -5
      englishthaonguyendethuong  đã bình luận lúc 10, Tháng 10, 2024, 9:45

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • 0
        kjkminh  đã bình luận lúc 21, Tháng 1, 2025, 14:02

        Thi chưachưa


    • -5
      nogo007akapkn  đã bình luận lúc 24, Tháng 6, 2024, 4:11

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -3
      quan08  đã bình luận lúc 17, Tháng 6, 2024, 6:10

      thi chưa


    • -20
      daoxuantien123  đã bình luận lúc 5, Tháng 11, 2023, 7:56 ← chỉnh sửa

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -7
    Cuunon311  đã bình luận lúc 9, Tháng 10, 2023, 15:30

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -22
    DoanHoangLong  đã bình luận lúc 6, Tháng 8, 2023, 8:46

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    vndkhoi  đã bình luận lúc 17, Tháng 6, 2023, 15:43 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -51
    how_to_get_her_love999  đã bình luận lúc 3, Tháng 5, 2023, 8:01

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -37
    FarisNya_2  đã bình luận lúc 9, Tháng 4, 2023, 15:54

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -79
    sickboy1368  đã bình luận lúc 7, Tháng 10, 2021, 14:03 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.