Truy vết xâu chung dài nhất
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho hai xâu ký tự $S$ và $T$ chỉ gồm các chữ cái tiếng Anh in thường. Hãy tìm xâu con chung dài nhất (LCS) của hai xâu. Nếu có nhiều xâu con chung có cùng độ dài lớn nhất, hãy in ra xâu có thứ tự từ điển nhỏ nhất. Nếu không có ký tự chung nào, in ra EMPTY.
Cấu trúc con tối ưu: tính bảng $dp[i][j]$ là độ dài LCS của hậu tố $S[i..]$ và $T[j..]$, sau đó tham lam chọn ký tự nhỏ nhất ở mỗi bước sao cho vẫn giữ được độ dài tối ưu.
Dữ liệu vào
Dòng đầu tiên chứa xâu $S$. Dòng thứ hai chứa xâu $T$.
Dữ liệu ra
Xâu con chung dài nhất có thứ tự từ điển nhỏ nhất, hoặc EMPTY nếu độ dài bằng 0.
Ví dụ
| Input | Output |
|---|---|
| abac caba |
aba |
| abc def |
EMPTY |
Giới hạn
$1 \le |S|, |T| \le 1000$.
Community Discussion