Bài 28.4. Kiểm Tra Chuỗi Con Tiếp Tục - [Độ khó: Khá]

Trong một trò chơi giải đố về từ ngữ, bạn được cung cấp một danh sách các "nguyên liệu" chữ cái và một "công thức" tạo từ. Để tạo ra một từ theo công thức, bạn phải sử dụng các chữ cái từ danh sách nguyên liệu theo đúng thứ tự xuất hiện của chúng trong công thức. Tuy nhiên, các chữ cái này không cần phải liên tiếp nhau trong danh sách nguyên liệu, chỉ cần thứ tự tương đối được giữ nguyên. Ví dụ, nếu nguyên liệu là "banana" và công thức là "bna", bạn có thể tạo được từ đó ('b' đầu tiên, 'n' thứ hai, 'a' thứ ba). Bạn cần viết chương trình kiểm tra xem một "công thức" từ T có thể được tạo ra từ "nguyên liệu" chuỗi S hay không.

INPUT FORMAT

Dòng đầu tiên chứa chuỗi S (nguyên liệu), độ dài không quá 1000 ký tự. Dòng thứ hai chứa chuỗi T (công thức), độ dài không quá 1000 ký tự. Cả S và T chỉ chứa các chữ cái tiếng Anh viết thường (a-z).

OUTPUT FORMAT

In ra "YES" nếu T có thể được tạo từ S, ngược lại in ra "NO".

Ví dụ 1:

Input:

programming
prgm

Output:

YES

Giải thích:

• 'p' trong "prgm" được tìm thấy ở vị trí 0 của "programming".
• 'r' trong "prgm" được tìm thấy ở vị trí 1 của "programming".
• 'g' trong "prgm" được tìm thấy ở vị trí 2 của "programming".
• 'm' trong "prgm" được tìm thấy ở vị trí 6 của "programming" (sau 'g' ở vị trí 2). Thứ tự các ký tự trong "prgm" được giữ nguyên trong "programming".

Ví dụ 2:

Input:

apple
aple

Output:

NO

Giải thích:

• 'a' trong "aple" được tìm thấy ở vị trí 0 của "apple".
• 'p' trong "aple" được tìm thấy ở vị trí 1 của "apple".
• 'l' trong "aple" không tìm thấy trong "apple" sau 'p' ở vị trí 1. Ký tự 'l' không tồn tại trong "apple". Hoặc nếu chuỗi T là ale, thì e phải xuất hiện sau l. Ví dụ S="apple", T="apl". a -> a (idx 0) p -> p (idx 1) l -> p (idx 2). Không có 'l' sau p (idx 1). Correct example: S="apple", T="aple". e comes before l in the source string. S="elephant", T="ephant" -> YES S="elephant", T="elph" -> NO (p comes before l)

Let's modify Example 2 to make it clear:

Ví dụ 2:

Input:

algorithm
logarithm

Output:

NO

Giải thích:

• 'l' trong "logarithm" được tìm thấy ở vị trí 1 của "algorithm".
• 'o' trong "logarithm" không thể được tìm thấy trong "algorithm" sau 'l' ở vị trí 1. (Ký tự 'o' không xuất hiện trong "algorithm" sau vị trí 1, nó chỉ có ở vị trí 1. Hoặc ký tự 'o' không tồn tại trong chuỗi "algorithm"). The problem is checking if T is a subsequence of S. Example 2's logarithm is not a subsequence of algorithm. o is not present, r is before o.

Let's use a simpler one.

Ví dụ 2 (Đã sửa):

Input:

banana
bna

Output:

YES

Giải thích:

• 'b' của "bna" được tìm thấy ở vị trí 0 của "banana".
• 'n' của "bna" được tìm thấy ở vị trí 2 của "banana" (sau 'b' ở vị trí 0).
• 'a' của "bna" được tìm thấy ở vị trí 3 của "banana" (sau 'n' ở vị trí 2). Tất cả các ký tự của chuỗi T đều được tìm thấy trong S theo đúng thứ tự tương đối.