Single Wildcard Pattern Matching

题意翻译

## 题目描述 现在你得到了两个字符串$s,t$，其中$s$字符串包含小写英文字母以及不多于一个的$*$号，而$t$字符串只包含小写英文字母。$s$字符串的长度为$n$，而$t$字符串的长度为$m$。 在$s$字符串中的$*$号可以被替换为任意一个仅含有小写字母字符串（当然也可以是空字符串），字符串中的其他字符不能被更改或者调换顺序。如果将$*$号替换为某个任意字符串之后，$s$字符串可以变成$t$字符串，那么我们称$s,t$两个字符串是匹配的。 例如，字符串$s=aba*aba$与字符串$abaaba,abacaba,abazzzaba$都是匹配的，但与字符串$abcaaba,ababa,luogu,aba?aba,aba1aba$都是不匹配的。 如果我们给出的字符串$s,t$是匹配的，输出$YES$，否则输出$NO$。 ## 输入输出格式 ### 输入格式 第一行是两个整数$n,m\left( 1\leqslant n,m\leqslant 2\cdot 10^5 \right) $，分别表示字符串$s$和字符串$t$的长度。 第二行包含一个长度为$n$的字符串$s$，保证字符串中只含有小写字母和不多于一个的$*$。 第三行包含一个长度为$m$的字符串$t$，保证字符串中只含有小写字母。 ### 输出格式 如果你可以通过字符串$s$得到字符串$t$，也就是说二者是匹配的，那么输出$YES$，否则输出$NO$。 ------------ ------------ ------------ 源码区： ``` ## 题目描述 现在你得到了两个字符串$s,t$，其中$s$字符串包含小写英文字母以及不多于一个的$*$号，而$t$字符串只包含小写英文字母。$s$字符串的长度为$n$，而$t$字符串的长度为$m$。 在$s$字符串中的$*$号可以被替换为任意一个仅含有小写字母字符串（当然也可以是空字符串），字符串中的其他字符不能被更改或者调换顺序。如果将$*$号替换为某个任意字符串之后，$s$字符串可以变成$t$字符串，那么我们称$s,t$两个字符串是匹配的。 例如，字符串$s=aba*aba$与字符串$abaaba,abacaba,abazzzaba$都是匹配的，但与字符串$abcaaba,ababa,luogu,aba?aba,aba1aba$都是不匹配的。 如果我们给出的字符串$s,t$是匹配的，输出$YES$，否则输出$NO$。 ## 输入输出格式 ### 输入格式 第一行是两个整数$n,m\left( 1\leqslant n,m\leqslant 2\cdot 10^5 \right) $，分别表示字符串$s$和字符串$t$的长度。 第二行包含一个长度为$n$的字符串$s$，保证字符串中只含有小写字母和不多于一个的$*$。 第三行包含一个长度为$m$的字符串$t$，保证字符串中只含有小写字母。 ### 输出格式 如果你可以通过字符串$s$得到字符串$t$，也就是说二者是匹配的，那么输出$YES$，否则输出$NO$。 ```

题目描述

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

题意翻译

## 题目描述 现在你得到了两个字符串$s,t$，其中$s$字符串包含小写英文字母以及不多于一个的$*$号，而$t$字符串只包含小写英文字母。$s$字符串的长度为$n$，而$t$字符串的长度为$m$。 在$s$字符串中的$*$号可以被替换为任意一个仅含有小写字母字符串（当然也可以是空字符串），字符串中的其他字符不能被更改或者调换顺序。如果将$*$号替换为某个任意字符串之后，$s$字符串可以变成$t$字符串，那么我们称$s,t$两个字符串是匹配的。 例如，字符串$s=aba*aba$与字符串$abaaba,abacaba,abazzzaba$都是匹配的，但与字符串$abcaaba,ababa,luogu,aba?aba,aba1aba$都是不匹配的。 如果我们给出的字符串$s,t$是匹配的，输出$YES$，否则输出$NO$。 ## 输入输出格式 ### 输入格式 第一行是两个整数$n,m\left( 1\leqslant n,m\leqslant 2\cdot 10^5 \right) $，分别表示字符串$s$和字符串$t$的长度。 第二行包含一个长度为$n$的字符串$s$，保证字符串中只含有小写字母和不多于一个的$*$。 第三行包含一个长度为$m$的字符串$t$，保证字符串中只含有小写字母。 ### 输出格式 如果你可以通过字符串$s$得到字符串$t$，也就是说二者是匹配的，那么输出$YES$，否则输出$NO$。 ------------ ------------ ------------ 源码区： ``` ## 题目描述 现在你得到了两个字符串$s,t$，其中$s$字符串包含小写英文字母以及不多于一个的$*$号，而$t$字符串只包含小写英文字母。$s$字符串的长度为$n$，而$t$字符串的长度为$m$。 在$s$字符串中的$*$号可以被替换为任意一个仅含有小写字母字符串（当然也可以是空字符串），字符串中的其他字符不能被更改或者调换顺序。如果将$*$号替换为某个任意字符串之后，$s$字符串可以变成$t$字符串，那么我们称$s,t$两个字符串是匹配的。 例如，字符串$s=aba*aba$与字符串$abaaba,abacaba,abazzzaba$都是匹配的，但与字符串$abcaaba,ababa,luogu,aba?aba,aba1aba$都是不匹配的。 如果我们给出的字符串$s,t$是匹配的，输出$YES$，否则输出$NO$。 ## 输入输出格式 ### 输入格式 第一行是两个整数$n,m\left( 1\leqslant n,m\leqslant 2\cdot 10^5 \right) $，分别表示字符串$s$和字符串$t$的长度。 第二行包含一个长度为$n$的字符串$s$，保证字符串中只含有小写字母和不多于一个的$*$。 第三行包含一个长度为$m$的字符串$t$，保证字符串中只含有小写字母。 ### 输出格式 如果你可以通过字符串$s$得到字符串$t$，也就是说二者是匹配的，那么输出$YES$，否则输出$NO$。 ```