Atcoder Educational DP Contest F - LCS - VNOJ: VNOI Online Judge

Atcoder Educational DP Contest F - LCS

Đ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.

1

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

bai hay qua

-2

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

...

0

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

100100101110011 11100101010101000111 11011000100 1010101001

13

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

xin upvote

2

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

4

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

}

-26

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

xin downvote

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

-1

hoanglongnguyen9002 đã bình luận lúc 16, Tháng 12, 2024, 13:10

ok

-21

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

thg nào de'o upvote cái này thì thằng đó gay vcl gay

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

7

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 :)))

-6

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.

-4

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

another reason to nerf chamber

-20

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

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

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

-6

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

thi chưa

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

-3

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

Thi chưachưa

-6

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

thi chưa

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

-4

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

thi chưa

-18

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.

-6

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

bai nay hay

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

-19

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

sao vote xuống nhiều vậy ?

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

-27

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.

-50

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

Anh em vote xuống cho tôi đi

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

-34

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

cảm ơn bạn nha, bạn không nói mình cũng biết rồi

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

-75

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

Xâu con chung dài nhất

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