trang chủ / bài tập / wildmatch

So khớp mẫu với một ký tự đại diện

Đề bài

Mô tả

Cho hai xâu st. Xâu s gồm các chữ cái Latinh thường và nhiều nhất một ký tự đại diện *; xâu t chỉ gồm các chữ cái Latinh thường. Độ dài của sn, độ dài của tm.

Ký tự * trong s (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 s được phép thay đổi. Nếu có thể thay ký tự * để biến s thành đúng xâu t thì ta nói t khớp với mẫu s.

Ví dụ, nếu s= aba*aba thì các xâu aba​aba, abacaba, abazzzaba khớp với mẫu, còn ababa, abcaaba, codeforces thì không.

Hãy in ra YES nếu t khớp với mẫu s, ngược lại in ra NO.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nm: độ dài của st.
  • Dòng thứ hai chứa xâu s độ dài n, 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 t độ dài m, 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 từ s, ngược lại in ra NO.

Ràng buộc

  • 1n,m2·105

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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0