Đan xen hai xâu

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

Draft saved