So khớp mẫu với một ký tự đại diện
Đề bài
Mô tả
Cho hai xâu và . Xâu gồm các chữ cái Latinh thường và nhiều nhất một ký tự đại diện *; xâu chỉ gồm các chữ cái Latinh thường. Độ dài của là , độ dài của là .
Ký tự * trong (nếu có) được phép thay bằng một dãy tùy ý (có thể rỗng) các chữ cái Latinh thường. Không ký tự nào khác của được phép thay đổi. Nếu có thể thay ký tự * để biến thành đúng xâu thì ta nói khớp với mẫu .
Ví dụ, nếu aba*aba thì các xâu abaaba, abacaba, abazzzaba khớp với mẫu, còn ababa, abcaaba, codeforces thì không.
Hãy in ra YES nếu khớp với mẫu , ngược lại in ra NO.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và : độ dài của và .
- Dòng thứ hai chứa xâu độ dài , gồm các chữ cái Latinh thường và nhiều nhất một ký tự
*. - Dòng thứ ba chứa xâu độ dài , chỉ gồm các chữ cái Latinh thường.
Dữ liệu ra
In ra YES nếu có thể thu được từ , ngược lại in ra NO.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 10 code*s codeforces |
YES | Thay * bằng force được codeforces. |
| 6 5 vk*cup vkcup |
YES | Thay * bằng xâu rỗng được vkcup. |
| 1 1 v k |
NO | Không có * và hai xâu khác nhau. |
| 9 6 gfgf*gfgf gfgfgf |
NO | Không cách thay * nào cho ra gfgfgf. |
Bình luận