DP-Xâu con chung

ĐỀ BÀI: XÂU CON CHUNG THEO THỨ TỰ DÀI NHẤT (LCS)

Cho hai xâu ký tự \(S\) và \(T\) có độ dài lần lượt là \(m\) và \(n\).

Yêu cầu: Tìm độ dài lớn nhất của một chuỗi con theo thứ tự (subsequence) xuất hiện đồng thời trong cả hai xâu \(S\) và \(T\).

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương \(m, n\) (\(0 < m, n \le 2500\)).
• Dòng thứ hai chứa xâu \(S\).
• Dòng thứ ba chứa xâu \(T\).

Dữ liệu ra:

• In ra một số nguyên duy nhất là độ dài của chuỗi con chung dài nhất.

Ví dụ:

Input

4 5
abcd
acdeg

Output

3

Giải thích: Chuỗi con chung dài nhất là acd, có độ dài là \(3\).