Xâu con chung dài nhất

Buổi 04 — Mảng 2D & Chuỗi Dynamic Programming
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề 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$.

Draft saved