Truy vết xâu chung dài nhất

Buổi 22 — DP 2D & LIS Dynamic Programming Strings
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved