Độ dài dãy con chung dài nhất của hai xâu ngắn
Dãy con của một xâu là xâu nhận được bằng cách xoá bớt một số ký tự nhưng giữ nguyên thứ tự
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, strings.
Nội dung đề bài
Mô tả bài toán
Dãy con của một xâu là xâu nhận được bằng cách xoá bớt một số ký tự nhưng giữ nguyên thứ tự các ký tự còn lại. Hai xâu càng "giống nhau" thì dãy con chung dài nhất càng dài, và bảng quy hoạch động hai chiều của bài này là khuôn mẫu cho rất nhiều bài so khớp xâu về sau.
Yêu cầu
Cho hai xâu chỉ gồm chữ cái thường. Hãy tính độ dài của dãy con chung dài nhất của hai xâu. Nếu hai xâu không có ký tự nào chung thì kết quả là 0.
Quy ước nộp bài
Nộp tệp solution.cpp đọc hai xâu từ stdin (mỗi xâu một dòng) và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: xâu thứ nhất a, độ dài từ 1 tới 20, không chứa dấu cách.
- Dòng thứ hai: xâu thứ hai b, độ dài từ 1 tới 20, không chứa dấu cách.
Output
- Một số nguyên trên một dòng: độ dài dãy con chung dài nhất.
Ràng buộc
- Ký tự chỉ là chữ cái thường a–z, không có dấu cách hay ký tự đặc biệt.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
abcde
ace
Output
3
Ví dụ 2
Input
abc
def
Output
0
Giải thích
Lấy a, c, e từ cả hai xâu theo đúng thứ tự nên dãy con chung dài nhất có độ dài 3. In ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
