solution

Trong một bộ phân tích từ vựng (lexer) đơn giản, trước khi xây dựng một động cơ regex đầy đủ, ta thường cần một bước kiểm tra sơ bộ xem một xâu có khớp với một mẫu (pattern) chứa ký tự đại diện hay không.

Cho một xâu $s$ chỉ gồm các chữ cái tiếng Anh viết thường, và một mẫu $p$ gồm chữ cái thường cùng hai ký tự đặc biệt:

• ? khớp với đúng một ký tự bất kỳ,
• * khớp với một dãy con bất kỳ (kể cả dãy rỗng) gồm các ký tự bất kỳ.

Hãy xác định mẫu $p$ có khớp toàn bộ (từ ký tự đầu tới ký tự cuối) xâu $s$ hay không.

Ví dụ 1: $s =$ abc, $p =$ a?c → khớp (? khớp với b).

Ví dụ 2: $s =$ abc, $p =$ a*d → không khớp (không có d ở cuối s).