A11871. Single Wildcard Pattern Matching
编程题
普及/提高-
知识点
题目描述
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 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.
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".
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".