trang chủ / đề bài / wildmatch

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

Đề bài

Mô tả

Cho hai xâu s và t. 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 s là n, độ dài của t là m.

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 n và m: độ dài của s và t.
  • 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

  • 1≤n,m≤2·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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0