Xâu con chung dài nhất
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề bài
Cho hai xâu $A$ và $B$ chỉ gồm các chữ cái tiếng Anh thường. Một xâu con chung (không nhất thiết liên tiếp) của $A$ và $B$ là xâu có thể thu được bằng cách xóa một số ký tự (có thể không xóa ký tự nào) từ $A$ và từ $B$. Hãy tìm độ dài của xâu con chung dài nhất (LCS) giữa $A$ và $B$, đồng thời in ra một xâu con chung dài nhất đó.
Dữ liệu vào
- Dòng đầu tiên chứa xâu $A$.
- Dòng thứ hai chứa xâu $B$.
Dữ liệu ra
- Dòng đầu tiên ghi một số nguyên là độ dài LCS.
- Dòng thứ hai ghi một xâu con chung dài nhất (nếu độ dài bằng $0$ thì không cần in thêm hoặc in dòng trống).
Ví dụ
| Input | Output |
|---|---|
| abcbdab bdcaba |
4 bcba |
Giới hạn
$1 \le |A|, |B| \le 2000$.
Community Discussion