Dãy con chung của ba xâu

Buổi 22 — DP 2D & LIS Dynamic Programming Strings
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho ba xâu ký tự $A$, $B$ và $C$ 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 xuất hiện trong cả ba xâu.

Cấu trúc con tối ưu: nếu $A_i = B_j = C_k$ thì $dp[i][j][k] = dp[i-1][j-1][k-1] + 1$, ngược lại là $\max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])$.

Dữ liệu vào

Ba dòng lần lượt chứa các xâu $A$, $B$, $C$.

Dữ liệu ra

Một số nguyên duy nhất là độ dài LCS của ba xâu.

Ví dụ
Input Output
abc123
1a2b3c
abc
3
geeks
geeksfor
geeksby
5
Giới hạn

$1 \le |A|, |B|, |C| \le 150$.

Draft saved