1023A.md (2474B)
1 Source: https://codeforces.com/problemset/problem/1023/A 2 3 A. Single Wildcard Pattern Matching 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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$. 24 25 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". 26 27 If the given string $t$ matches the given string $s$, print "YES", otherwise print "NO". 28 29 Input 30 31 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. 32 33 The second line contains string $s$ of length $n$, which consists of lowercase Latin letters and at most one wildcard character '*'. 34 35 The third line contains string $t$ of length $m$, which consists only of lowercase Latin letters. 36 37 Output 38 39 Print "YES" (without quotes), if you can obtain the string $t$ from the string $s$. Otherwise print "NO" (without quotes). 40 41 Examples 42 43 Input 44 45 ``` 46 6 10 47 code*s 48 codeforces 49 ``` 50 51 Output 52 53 ``` 54 YES 55 ``` 56 57 Input 58 59 ``` 60 6 5 61 vk*cup 62 vkcup 63 ``` 64 65 Output 66 67 ``` 68 YES 69 ``` 70 71 Input 72 73 ``` 74 1 1 75 v 76 k 77 ``` 78 79 Output 80 81 ``` 82 NO 83 ``` 84 85 Input 86 87 ``` 88 9 6 89 gfgf*gfgf 90 gfgfgf 91 ``` 92 93 Output 94 95 ``` 96 NO 97 ``` 98 99 Note 100 101 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". 102 103 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". 104 105 There is no wildcard character '*' in the third example and the strings "v" and "k" are different so the answer is "NO". 106 107 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".