Dãy con chung dài nhất

Buổi 22 — DP 2D & LIS Dynamic Programming Strings
Points
12
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 độ 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$.

Draft saved