#2054. LCS

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Free Contest 7

Cho xâu kí tự a có độ dài m , xâu kí tự b có độ dài n . Tìm dãy con chung dài nhất của hai xâu này.

Dãy con của một xâu là xâu thu được bằng cách xóa đi (hoạc có thể không xóa ký tự nào) một số kí tự từ xâu ban đầu nhưng vẫn giữ nguyên thứ tự của các kí tự còn lại.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương m n\ (1 ≤ m, n ≤ 2500) ;
  • Dòng thứ hai chứa xâu a ;
  • Dòng cuối cùng chứa xâu b .

Dữ liệu ra:

  • In ra độ dài của dãy con chung dài nhất tìm được.

Ví dụ:

Dữ liệu vào:
4 3
BBUS
UII
Dữ liệu ra:
1
Dữ liệu vào:
19 16
UAPJHVVJLRILRKULEAH
FAOIPJZLLKLUEGLE
Dữ liệu ra:
9
Dữ liệu vào:
4 3
EFSS
LEJ
Dữ liệu ra:
1
Dữ liệu vào:
10 10
DGBLRRUSXU
ODGBLDRRXU
Dữ liệu ra:
8
Dữ liệu vào:
14 14
MJAORPFSGHUHDB
MJRDFQSSGSHHDB
Dữ liệu ra:
10