← 返回题目列表

Codeforces · 1023/A

A. 单通配符模式匹配

中文机器翻译题面 查看原题

给定两个字符串 $$$s$$$ 和 $$$t$$$。字符串$$$s$$$由小写拉丁字母和最多1个通配符“*”组成,字符串$$$t$$$仅由小写拉丁字母组成。字符串$$$s$$$的长度等于$$$n$$$,字符串$$$t$$$的长度等于$$$m$$$。

The wildcard character '*' in the string $$$s$$$ (if any) can be replaced with an arbitrary sequence (possibly empty) of lowercase Latin letters. $$$s$$$ 中的任何其他字符都不能替换为任何内容。 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".

如果给定字符串 $$$t$$$ 与给定字符串 $$$s$$$ 匹配,则打印“YES”,否则打印“NO”。

输入

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 '*'.

第三行包含长度为$$$m$$$的字符串$$$t$$$,仅由小写拉丁字母组成。

输出

如果可以从字符串 $$$s$$$ 中获取字符串 $$$t$$$,则打印“YES”(不带引号)。否则打印“NO”(不带引号)。

示例

输入 #1

6 10
code*s
codeforces

输出 #1

YES

输入 #2

6 5
vk*cup
vkcup

输出 #2

YES

输入 #3

1 1
v
k

输出 #3

NO

输入#4

9 6
gfgf*gfgf
gfgfgf

输出#4

NO

注意

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".

在第二个示例中,通配符“*”可以替换为空字符串。 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".