codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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