Cho xâu kí tự \(A\) có độ dài \(m\), và 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 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.
Input
- Dòng đầu tiên chứa hai số nguyên dương \(m\) và \(n\) (\(1 \le m, n \le 2500\)).
- Dòng tiếp theo chứa xâu \(A\).
- Dòng tiếp theo chứa xâu \(B\).
Output
- In ra độ dài của dãy con chung dài nhất tìm được.
Example
Test 1
Input
7 7
AGGTAB
GXTXAYBOutput
4Note
Với ví dụ 1: LCS có độ dài 4, ví dụ: "GTAB".
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.