Độ dài dãy con chung

Bối cảnh và bài toán

Hai chuỗi ghi log có thể bị chèn/xóa ký tự. Một dãy con giữ nguyên thứ tự nhưng không cần liên tiếp.

Yêu cầu

Tìm độ dài dãy con chung dài nhất của hai chuỗi.

Input

Hai dòng lần lượt chứa s và t.

Output

In độ dài LCS.

Ràng buộc

• 1 <= |s|,|t| <= 3000
• Chuỗi gồm chữ cái thường.

Chấm điểm

Ví dụ 1

Input

axyb
abyxb

Output

3

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

abc
def

Output

0

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Gợi ý

Trước khi code, hãy viết rõ ý nghĩa của trạng thái, các trạng thái tiền nhiệm và thứ tự tính sao cho mọi dependency đã có giá trị.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from AtCoder Educational DP Contest F – LCS. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.