Độ dài xâu con chung dài nhất

Xem dạng PDF
Gửi bài giải
Điểm: 10,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho hai xâu ký tự ~X~ và ~Y~ chỉ bao gồm các chữ cái từ 'A' đến 'Z'. Hãy tìm độ dài xâu con chung dài nhất của hai xâu này.

Yêu cầu:
  • Xâu con không nhất thiết phải liên tiếp trong chuỗi gốc nhưng phải giữ nguyên thứ tự xuất hiện.
  • Chỉ cần tìm độ dài của xâu con chung dài nhất, không cần xuất ra xâu đó.
Dữ liệu vào:
  • Dòng 1: Một xâu ~X~ có độ dài từ 1 đến 1000.
  • Dòng 2: Một xâu ~Y~ có độ dài từ 1 đến 1000.
Dữ liệu ra:
  • In ra một số nguyên là độ dài của xâu con chung dài nhất.
Ví dụ:

Input

ACDBE
ABCDE

Output

4
Giải thích:
  • "ACDE" là xâu con chung dài nhất của "ACDBE" và "ABCDE", độ dài là 4. Điểm số:
  • 100% số điểm nếu tìm đúng độ dài xâu con chung dài nhất trong thời gian tối ưu.

Bình luận

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