Đan xen hai xâu
Points
34
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. Xâu $C$ được gọi là xâu đan xen của $A$ và $B$ nếu có thể phân hoạch các ký tự của $C$ thành hai dãy con không giao nhau sao cho dãy thứ nhất tạo thành $A$ và dãy thứ hai tạo thành $B$ (giữ nguyên thứ tự).
Cấu trúc con tối ưu: $dp[i][j]$ cho biết $i$ ký tự đầu của $A$ và $j$ ký tự đầu của $B$ có thể đan xen thành $i+j$ ký tự đầu của $C$ hay không.
Dữ liệu vào
Ba dòng lần lượt chứa các xâu $A$, $B$ và $C$.
Dữ liệu ra
In ra YES nếu $C$ là xâu đan xen của $A$ và $B$, ngược lại in ra NO.
Ví dụ
| Input | Output |
|---|---|
| aabcc dbbca aadbbcbcac |
YES |
| aabcc dbbca aadbbbaccc |
NO |
Giới hạn
$1 \le |A|, |B| \le 1000$, $1 \le |C| \le 2000$.
Community Discussion