Dãy con chung dài nhất
Points
12
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 độ dài của xâu con chung dài nhất (LCS) của $S$ và $T$. Xâu con của một xâu thu được bằng cách xóa đi một số ký tự (có thể không liên tiếp) mà vẫn giữ nguyên thứ tự.
Cấu trúc con tối ưu: nếu $S_i = T_j$ thì $dp[i][j] = dp[i-1][j-1] + 1$, ngược lại $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$.
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
Một số nguyên duy nhất là độ dài của xâu con chung dài nhất.
Ví dụ
| Input | Output |
|---|---|
| abcde ace |
3 |
| abc def |
0 |
Giới hạn
$1 \le |S|, |T| \le 1000$.
Community Discussion