Задано две строки $$$s$$$ и $$$t$$$. Строка $$$s$$$ состоит из строчных букв латинского алфавита и не более одного символа звездочки '*', строка $$$t$$$ состоит только из строчных букв латинского алфавита. Длина строки $$$s$$$ равна $$$n$$$, длина строки $$$t$$$ равна $$$m$$$.
Символ зведочки '*' в строке $$$s$$$ (если он есть) можно заменить на произвольную последовательность символов (возможно, пустую) строчных латинских букв. Другие символы строки $$$s$$$ ни на что заменять нельзя. Если после такой замены в $$$s$$$ можно получить строку $$$t$$$, то говорят, что строка $$$t$$$ соответствует шаблону $$$s$$$.
Например, если $$$s=$$$«aba*aba», то такому шаблону соответствуют строки «abaaba», «abacaba», «abazzzzaba», но не соответствуют строки «ababa», «abcaaba», «codeforces», «aba1aba», «aba?aba».
Если строка $$$t$$$ из соответствует шаблону $$$s$$$, выведите «YES», иначе выведите «NO».
В первой строке входных данных записано два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина строки $$$s$$$ и длина строки $$$t$$$ соответственно.
Во второй строке входных данных записана строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита и не более одного символа звездочки '*'.
В третьей строке входных данных записана строка $$$t$$$ длины $$$m$$$, состоящая только из строчных букв латинского алфавита.
Выведите «YES» (без кавычек), если можно получить строку $$$t$$$ из строки $$$s$$$. В противном случае выведите «NO» (без кавычек).
6 10
code*s
codeforces
YES
6 5
vk*cup
vkcup
YES
1 1
v
k
NO
9 6
gfgf*gfgf
gfgfgf
NO
В первом тестовом примере символ звездочки '*' может быть заменен строкой «force». Таким образом, строка $$$s$$$ после этой замены будет равна «codeforces», а ответ «YES».
Во втором тестовом примере символ звездочки '*' может быть заменен пустой строкой. Таким образом, строка $$$s$$$ после этой замены будет равна «vkcup», а ответ «YES».
В третьем тестовом примере нет символа звездочки '*', а строки «v» и «k» не равны, таким образом ответ «NO».
В четвертом тестовом примере не существует такой замены символа звездочки '*', что вы сможете получить строку $$$t$$$, таким образом ответ «NO».
Название |
---|