Dãy con chung của ba xâu
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$.
Community Discussion