Xâu con chung liên tiếp dài nhất

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

Draft saved