Bài 26.4. Tìm kiếm Văn bản với Ký tự Đại diện - [Độ khó: Khó]

Bạn được giao nhiệm vụ phát triển một tính năng tìm kiếm nâng cao cho một trình soạn thảo văn bản. Tính năng này cho phép người dùng tìm kiếm chuỗi con trong một văn bản lớn bằng cách sử dụng các ký tự đại diện (wildcard characters). Cụ thể, bạn cần hỗ trợ hai loại ký tự đại diện:

• ?: khớp với bất kỳ một ký tự nào.
• *: khớp với không hoặc nhiều ký tự bất kỳ.

Chương trình của bạn sẽ nhận một chuỗi văn bản (text) và một chuỗi mẫu (pattern) chứa các ký tự đại diện. Bạn cần xác định xem toàn bộ chuỗi text có khớp với pattern hay không.

INPUT FORMAT

Hai dòng đầu vào: Dòng 1: Chuỗi text (độ dài tối đa 1000 ký tự). Dòng 2: Chuỗi pattern (độ dài tối đa 1000 ký tự). Các chuỗi chỉ chứa các ký tự chữ cái tiếng Anh thường và hoa, số, và các ký tự đại diện ?, *.

OUTPUT FORMAT

In ra TRUE nếu text khớp với pattern, ngược lại in FALSE.

Ví dụ:

Input:

abcde
a*e

Output:

TRUE

Giải thích:

• a khớp với a.
• * khớp với bcd (nhiều ký tự).
• e khớp với e.

Input (ví dụ khác):

ab
a?

Output:

TRUE

Giải thích:

• a khớp với a.
• ? khớp với b.

Input (ví dụ khác):

adceb
a*b

Output:

TRUE

Giải thích:

• a khớp với a.
• * khớp với dce.
• b khớp với b.

Input (ví dụ khác):

mississippi
m?ss*pp*

Output:

TRUE

Giải thích:

• m khớp với m.
• ? khớp với i.
• ss khớp với ss.
• * khớp với iss.
• pp khớp với pp.
• * khớp với i.

Input (ví dụ khác):

abc
ab

Output:

FALSE

Giải thích: text dài hơn pattern và không có ký tự đại diện ở cuối để khớp phần còn lại.

Input (ví dụ khác):

a
*

Output:

TRUE

Giải thích: * có thể khớp với 0 hoặc nhiều ký tự, ở đây nó khớp với a.

Input (ví dụ khác):

aaa
a*a

Output:

TRUE

Giải thích: * khớp với a ở giữa.