Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
A
Single Wildcard Pattern Matching
Codeforces
1200
原题
←B →
翻译中…

You are given two strings $s$ and $t$. The string $s$ consists of lowercase Latin letters and at most one wildcard character '*', the string $t$ consists only of lowercase Latin letters. The length of the string $s$ equals $n$, the length of the string $t$ equals $m$.

翻译中…

The wildcard character '*' in the string $s$ (if any) can be replaced with an arbitrary sequence (possibly empty) of lowercase Latin letters. No other character of $s$ can be replaced with anything. If it is possible to replace a wildcard character '*' in $s$ to obtain a string $t$, then the string $t$ matches the pattern $s$.

翻译中…

For example, if $s=$"aba*aba" then the following strings match it "abaaba", "abacaba" and "abazzzaba", but the following strings do not match: "ababa", "abcaaba", "codeforces", "aba1aba", "aba?aba".

翻译中…

If the given string $t$ matches the given string $s$, print "YES", otherwise print "NO".

翻译中…

Input

翻译中…

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the string $t$, respectively.

翻译中…

The second line contains string $s$ of length $n$, which consists of lowercase Latin letters and at most one wildcard character '*'.

翻译中…

The third line contains string $t$ of length $m$, which consists only of lowercase Latin letters.

翻译中…

Output

翻译中…

Print "YES" (without quotes), if you can obtain the string $t$ from the string $s$. Otherwise print "NO" (without quotes).

翻译中…

Note

翻译中…

In the first example a wildcard character '*' can be replaced with a string "force". So the string $s$ after this replacement is "codeforces" and the answer is "YES".

翻译中…

In the second example a wildcard character '*' can be replaced with an empty string. So the string $s$ after this replacement is "vkcup" and the answer is "YES".

翻译中…

There is no wildcard character '*' in the third example and the strings "v" and "k" are different so the answer is "NO".

翻译中…

In the fourth example there is no such replacement of a wildcard character '*' that you can obtain the string $t$ so the answer is "NO".

翻译中…

样例

Input #1
6 10
code*s
codeforces
Output #1
YES
InputCopy OutputCopy
Input #2
6 5
vk*cup
vkcup
Output #2
YES
InputCopy OutputCopy
Input #3
1 1
v
k
Output #3
NO
InputCopy OutputCopy
Input #4
9 6
gfgf*gfgf
gfgfgf
Output #4
NO
InputCopy OutputCopy
题目信息
题号
1023A
时间限制
1 s
内存限制
256 MB
标签
暴力
模拟
字符串

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。