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:
NoobCpp
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à 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

Comments

Please read the guidelines before commenting.


  • 1
    xthavan  commented on Oct. 30, 2024, 1:53 p.m.

    100100101110011 11100101010101000111 11011000100 1010101001


  • 8
    van353735  commented on Sept. 2, 2024, 11:59 a.m.

    xin upvote


  • 2
    sitingfake  commented on Aug. 24, 2024, 1:09 p.m.

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


    • 2
      Groot  commented on Sept. 2, 2024, 1:31 p.m.

      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];

      }


  • -11
    vdtue  commented on Aug. 20, 2024, 2:27 p.m.

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


  • -9
    phmducctintdn  commented on Aug. 14, 2024, 9:19 a.m.

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


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

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


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

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


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

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


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

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


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

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


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

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


  • -25
    vndkhoi  commented on June 17, 2023, 3:43 p.m. ← edited

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


  • -42
    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.


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

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


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

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