CF1023A.Single Wildcard Pattern Matching

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输入格式

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.

输出格式

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

输入输出样例

输入#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".

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

首页