Xâu con chung liên tiếp dài nhất
Points
26
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 liên tiếp chung dài nhất (Longest Common Substring) xuất hiện ở cả hai xâu.
Cấu trúc con tối ưu: $dp[i][j]$ là độ dài xâu con liên tiếp chung kết thúc tại $S_i$ và $T_j$; nếu $S_i = T_j$ thì $dp[i][j] = dp[i-1][j-1] + 1$, ngược lại $dp[i][j] = 0$.
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 xâu con liên tiếp chung dài nhất.
Ví dụ
| Input | Output |
|---|---|
| abcdef zbcdf |
3 |
| abc def |
0 |
Giới hạn
$1 \le |S|, |T| \le 3000$.
Community Discussion